As an example, we will use the following undirected weighted graph:
We are looking for the shortest weighted path between nodes A and E.
The different steps are as follows:
- Initialization (the first row of the table): We initialize the distances between the starting node A and all the other nodes to infinity, except the distance from A to A, which is set to 0.
- The first iteration (the second row of the following table):
- Starting from node A, the algorithm traverses the graph toward each of the neighbors of A, B, C, and D.
- It remembers the distance from the starting node A to each of the other nodes. If we're interested only in the shortest path length, we would only need the distance. But if we also want to know which nodes the shortest path is made of, we also need to keep the information about the incoming node (the parent). The reason will become clearer in the coming iterations. In this iteration, since we started from...
