Dijkstra’s Algorithm allows you to calculate the shortest path between one node of your choosing and every other node in a graph.
Here’s how the algorithm is implemented:
Mark all nodes as unvisited.
Mark the selected initial node with a current distance of 0 and the rest with infinity.
Set the initial node as current node.
For the current node, consider all of its unvisited neighbors and calculate their distances by adding the current distance of current node to the weight of the edge connecting neighbor node and current node.
Compare the newly calculated distance to the current distance assigned to the neighboring node and set is as the new current distance of neighboring node.
When done considering all of the unvisited neighbors of the current node, mark the current node as visited.
If the destination node has been marked visited then stop. The algorithm has finished.
Otherwise, select the unvisited node that is marked with the smallest distance, set it as the new current node, and go back to step 4.
Let’s take a look at an illustration implementing Dijkstra’s to understand the algorithm better!
Dijkstra’s Algorithm has several real-world use cases, including the following:
View all Courses