Bellman-Ford Algorithm

Description

Prim’s algorithm is a well-known algorithm used for finding the minimum spanning tree in a weighted undirected graph. It is named after its inventor, Jarník and Prim, who independently developed it in 1930. Prim’s algorithm is a greedy algorithm that starts with a single vertex and adds one edge at a time to form a tree. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The process continues until all vertices are connected, and a minimum spanning tree is formed.

To implement Prim’s algorithm, the following steps are necessary:

• Initialize the minimum spanning tree with a single vertex selected at random from the graph.
• Find all edges that connect the tree to vertices that are not yet in the tree.
• Select the edge with the smallest weight from the set of edges found in step 2 and add it to the minimum spanning tree.
• Add the new vertex that is connected to the selected edge to the minimum spanning tree.
• Repeat steps 2–4 until all vertices are part of the minimum spanning tree.

Key Features

• Minimum Total Cost Spanning: Prim’s algorithm ensures that all nodes (e.g., VMs, routers) in a network are connected with the minimum total cost (e.g., latency, bandwidth usage).
• Edge-by-Edge Growth: Starts with a single node and greedily adds the next minimum edge that connects a new node to the growing tree.
• Supports Dense Graphs Efficiently: Particularly effective in dense graphs (like full-mesh tenant overlays) where many VMs are interconnected.
• Time complexity: O(E log V)

Use Case

In multicast or broadcast communication, sending messages to multiple VMs or tenants without redundancy is essential. OpenStack (via Neutron or SDN controllers) needs to minimize total network cost (latency, bandwidth, or hops).

OpenStack virtual networks form a graph with switches, routers, VMs, and links with weights (delay, bandwidth). Unlike Dijkstra (which finds shortest path from a single source), Prim’s algorithm builds a cost-efficient routing backbone (MST) that can connect multiple components with minimum overhead.

A set of users (or front-end gateways) need to be connected to a distributed set of VMs or compute nodes. You model this as a graph with weighted edges (cost of assigning a user to a VM: based on latency, load, or location).

Implementation

Below is the implimentation of leetcode solution for Min Cost to Connect All Points (Leetcode 1584).

References

• GeeksForGeeks: https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
• Wikipedia: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm