30 Days of Algorithms: From Zero to Intermediate (23/30) —Dijkstra’s Algorithm

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

Imagine a map where cities are represented by nodes and roads connecting them are edges. The weights on the edges could represent distance, travel time, or even cost. Dijkstra’s algorithm finds the shortest path between a starting point and any node in the graph.

Example

Here’s the graph where we will find the shortest path from A to E.

Graph example

Algorithm

We will create a table to store information about all nodes. This table will include the shortest distance to each node and the node that came before it in the path.

Initial table

Now we will prepare two lists — visited and unvisited nodes.

visited = []
unvisited [A, B, C, E, F, G]

Step 1