I have a graph in which I have to find the shortest path from A to H(There are A…H edges).
Weights:
A-B: 3
A-C: 5
B-C: 1
B-F: 1
C-F: 1
The problem arises when I reach (select) B. B-C is 1 and B-F is 1.
For the next step, if I select C, the path will eventually be longer than if I go B-F. How do I decide which point to select?
Edit:
In the image, we can see the obvious shortest path is a-b-f-e-h (total weight being 9).
If we go via C, the path would be a-b-c-f-e-h (total weight being 11).
Best Answer
It doesn't matter which one you select, the algorithm will always find a shortest path. The only difference is that it might find a different path of equal length if you make a different choice here.
So the step by step solution in this case is: Initially, the distance to A is 0 and all other distances are infinite.
Next A is the closest unvisited node, so we mark A visited and set the distances:
$B = \min\{3,\infty\}=3$
$C = \min\{5,\infty\}=5$
$D = \min\{6,\infty\}=6$
Next B is the closest unvisited node, so we mark B visited and set the distances:
$C = \min\{3+1,5\}=4$
$E = \min\{3+5,\infty\}=8$
$F = \min\{3+1,\infty\}=4$
At this point we could choose either C or F, so lets choose C. So we mark C as visited and set the distances:
$D = \min\{4+2,6\}=6$
$F = \min\{4+2,4\}=4$
Note that in the last step, we didn't change the path to F. The old path to F was shorter. Now we pick F, since this is the unique node that is the minimum distance univisited node. So we set F to visited and set:
$E = \min\{4+2,8\}=6$
$G = \min\{4+4,\infty\}=8$
$H = \min\{4+8,\infty\}=12$
After this, we visit D and E (in arbitrary order), then G and finally H will be the unvisited node with the minimum distance, so then we will finally visit H.