Now we need to implement our algorithm.
At our starting node (X), we have the following choice:
- Visit A next at a cost of 7
- Visit B next at a cost of 2
- Visit C next at a cost of 3
- Visit E next at a cost of 4
We choose the lowest cost option, to visit node B at a cost of 2.
We then have the following options:
- Visit A from X at a cost of 7
- Visit A from B at a cost of (2 + 3) = 5
- Visit D from B at a cost of (2 + 4) = 6
- Visit H from B at a cost of (2 + 5) = 7
- Visit C from X at a cost of 3
- Visit E from X at a cost of 4
The next lowest cost item is visiting C from X, so we try that and then we are left with the above options, as well as:
- Visit L from C at a cost of (3 + 2) = 5
Next we would visit E from X as the next lowest cost is 4.
For each destination node that we visit, we note the possible next destinations and the total weight to visit that destination. If a destination is one we have seen before and the weight to visit is lower than it was previously, this new weight will take its place. For example
- Visiting A from X is a cost of 7
- But visiting A from X via B is a cost of 5
- Therefore we note that the shortest route to X is via B
We only need to keep a note of the previous destination node and the total weight to get there.
We continue evaluating until the destination node weight is the lowest total weight of all possible options.
In this trivial case it is easy to work out that the shortest path will be:
X -> B -> H -> G -> Y
For a total weight of 11.
In this case, we will end up with a note of:
- The shortest path to Y being via G at a weight of 11
- The shortest path to G is via H at a weight of 9
- The shortest path to H is via B at weight of 7
- The shortest path to B is directly from X at weight of 2
And we can work backwards through this path to get all the nodes on the shortest path from X to Y.
Once we have reached our destination, we continue searching until all possible paths are greater than 11; at that point we are certain that the shortest path is 11.