Dijkstra's Algorithm and Visualizer

Dijkstra’s Algorithm is used for finding the shortest path between nodes in a graph

How Dijkstra’s Algorithm Works

Dijkstra’s Algorithm operates by maintaining a set of nodes whose shortest distance from the source is known and a set of nodes whose shortest distance from the source is unknown. Here's a step-by-step breakdown of how it works:

1. Initialization:

   • Start with the source node. Set the distance to the source node as 0, and set all other nodes' distances to infinity (∞).

   • Mark all nodes as unvisited.

2. Visiting Nodes:

   • Start with the source node. Visit all of its neighbors and calculate their tentative distances (i.e., the sum of the source node's distance and the weight of the edge connecting to the neighbor).

   • Update the neighbor's distance if the newly calculated distance is smaller than its current distance.

   • After visiting all neighbors, mark the source node as visited.

3. Choosing the Next Node:

   • From the unvisited nodes, choose the node with the smallest tentative distance.

   • Repeat the process of visiting its neighbors and updating distances.

   • Continue until all nodes have been visited or the smallest tentative distance among the unvisited nodes is infinity (indicating that there is no path to remaining nodes).

4. Termination:

   • The algorithm terminates when all nodes have been visited. The shortest path to each node is now known.

Food for thought: What would be the potential modifications to Dijkstra’s algorithm if we want to find the k-th shortest path instead of just the shortest path? Let me know your thoughts and suggestions via comments!