What is Dijkstra’s algorithm, and how is it implemented?

Wyatt Saltzman

2 min readMay 8, 2021

TLDR

Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph.

Sudocode:

function dijkstra(G, S)

for each vertex V in G

distance[V] <- infinite

previous[V] <- NULL

If V != S, add V to Priority Queue Q

distance[S] <- 0

while Q IS NOT EMPTY

U <- Extract MIN from Q

for each unvisited neighbour V of U

tempDistance <- distance[U] + edge_weight(U, V)

if tempDistance < distance[V]

distance[V] <- tempDistance

previous[V] <- U

return distance[], previous[]

Further Explained

The shortest-path tree is found with the given root. The algorithm then uses two sets one containing the vertices and the other with the vertices not yet used in the shortest path tree. Throughout the algorithm, it finds a vertex that is not yet included in the shortest path tree and has a minimum distance from the source.

To do this you can follow these steps:

Create a set called SPT, that is used to keep track of the vertices in the shortest path tree. At the start this set is empty.
Make a distance value for every vertice in the input graph and initialize them to infinite. Except for the source vertex, you assign it to zero so it is picked first.
While SPT is doesn’t have all the vertices