In a book I am working through I have been given a problem where a graph represents an electronic information network. The vertices are computer installations and the arcs/edges are direct links between them. The weights on the edges are data rates [the higher the number, the faster the link].
The question is asking me to modify Dijkstra's algorithm to allow me to find the fastest path from A to G. [NOT the shortest path].
The graph is attached below.
My initial approach was to only replace the current working value if the new one was larger [as opposed to replacing it when it was smaller]. Using this approach I came up with a path of ADEFG. This path gives a speed of 8 [speed of path is that of the lowest speed in the path].
However, after checking my result, I found the answer was a path of ABCFG with a speed of 9. I do not understand how they achieved this and their explanation is not in the least bit clear. Here it is:
"Working values are computed by the following:
Compute min(label, link) and replace working value if this is bigger than the current working value. The vertex to be labelled is that with the largest working value."
I am at a loss as to how they achieved a path of ABCFG - everything I have tried keeps giving me ADEFG. Can anyone explain the explanation given and show me how ABCFG is attained?
Thank you for your help.