Unpacking Dijkstra’s Algorithm: A Deep Dive into its Mechanism and Real-Life Applications

Introduction to the shortest path problem

The shortest path problem is a classic problem in graph theory, which consists of finding the shortest path between two vertices of a weighted graph. A graph is a mathematical structure composed of nodes (or vertices) connected by edges (or links). Graphs can be directed or not, depending on whether the edges have a direction or not. In a weighted graph, each edge has a value called a weight, which typically represents the distance or cost associated with that connection.

Dijkstra’s algorithm

Dijkstra’s algorithm, invented by Edsger W. Dijkstra in 1956, is one of the best-known solutions to this problem. This is a greedy algorithm that progressively constructs a subgraph containing the minimum distances from a source vertex to all other vertices in the graph.

To understand how this algorithm works, we will use a concrete example involving cities as nodes and road distances as weights.

Practical example: road network between cities

Let’s imagine that we have the following road network:

• City A: point of origin
• City B: distance 10 km from A
• City C: distance 20 km from A, 5 km from B
• City D: distance 30 km from A, 15 km from B, 10 km from C

Steps of Dijkstra’s algorithm

Dijkstra’s algorithm follows the following steps:

1. Initialization: each vertex is assigned a provisional value corresponding to the distance between this vertex and the point of origin. For the origin point, this value is zero. For all other vertices, it is infinite.
2. Selection of the unvisited node with the smallest provisional value (we initially choose the point of origin).
3. For each neighbor of the selected node:
   1. Calculate the new distance passing through the selected node.
   2. Update the provisional value if this new distance is less than the old one.
4. Mark the selected node as visited.
5. Repeat steps 2 to 4 until all nodes are visited or the desired destination is reached.

Illustration of the steps with our concrete example

In our example, we are looking for the shortest path between city A (origin point) and city D (destination). Here is how Dijkstra’s algorithm works:

Step 1: Initialization