Just like Prim’s Algorithm, the MST is also the shortest path.
It is also a greedy algorithm.
Same as prim’s algorithm:
The tree starts from an arbitrary root vertex r and grows until it spans all the vertices in V.
- Pick an arbitrary vertex as starting point, since all vertex must be in the MST, it doesn’t matter which vertex should we start.
- Push all vertex to a priority queue and set key to infinity except the chosen vertex.
- Decrease the weight of adjacency vertex to the weight of the edge, can extract the smallest one.
- Repeat, until there’s no vertex in the queue.
Link to original
- Running time:
Dijkstra’s algorithm takes time, with the time dominated by the time spent in priority queue.
- Bellman-Ford algorithm, also a shortest path algorithm.