Dijkstra’s algorithm

What

Just like Prim’s Algorithm, the MST is also the shortest path.
It is also a greedy algorithm.

How

Same as prim’s algorithm:

How

The tree starts from an arbitrary root vertex r and grows until it spans all the vertices in V.

1. Pick an arbitrary vertex as starting point, since all vertex must be in the MST, it doesn’t matter which vertex should we start.
2. Push all vertex to a priority queue and set key to infinity except the chosen vertex.
3. Decrease the weight of adjacency vertex to the weight of the edge, can extract the smallest one.
4. Repeat, until there’s no vertex in the queue.

• Running time: $O(E\lg V)$

Link to original

Dijkstra’s algorithm takes $O(V^2)$ time, with the time dominated by the time spent in priority queue.

Links

• Bellman-Ford algorithm, also a shortest path algorithm.