# Thread: How to modify Dijkstra's Algorithm to find the fastest path between 2 points...

1. ## How to modify Dijkstra's Algorithm to find the fastest path between 2 points...

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?

2. First iteration
A,0 A->B,11 A->D,20 A->C,6

Second expand D
A,0 A->D,20 | A->B,11 A->D->G,6 A->D->F,2 A->D->E,8

Expand B
A,0 A->D,20 A->B,11 | A->B->C,9 A->B->G,7 A->D->F,2 A->D->E,8

Expand C
A,0 A->D,20 A->B,11 A->B->C,9 | A->B->G,7 A->B->C->F,9 A->D->E,8

Expand F
A,0 A->D,20 A->B,11 A->B->C,9 A->B->C->F,9 | A->B->C->F->G,9 A->B->C->F->E,9

Expand G, done

This is what I got... to the left of the | are the found shortest routes to points expanded, and to the right are the temporaries... Your approach works, you must've made a small mistake in the calculation somewhere.

Make sure you also expand the largest one first, not the smallest.

3. OK, I follow what you did and have reproduced it myself and confirmed it works.

However, I am a little puzzled by how this works, since it goes against how the book taught me to apply Dijkstra's algorithm.

In your method, for example, you go from A -> B -> C and mark that as 9. My learning of Dijkstra's says the working value should be A -> B + B -> C, giving 20. Using the method I have been taught and choosing the larger rather than lower working value, I would never get ABCFG.

Is using the weight of just the edge connecting the vertex [rather than as a sum of the edges leading to a vertex] the modification I needed?

Sorry if this makes no sense, I hate not understanding something and it appears the book has taught me one thing, then asked me to do something completely different in order to solve the problem. :/

4. Ah yes, that is exactly the idea in this problem, taking the max over a->b and b->c instead of adding these.

In this problem you are no dealing with the length of a path but with the stream over a path. Think of each connection as an internet cable allowing n mbps data to be downloaded. If connection a->b->c has in between it two cables, one that allows 11 and one that allows 9, the fastest you'll be able to download is 9.

You can also think of it as a highway with n tracks, the speed of a stream of cars will be dependent on the smallest number of tracks, if for example a road has one track for a mile and then 100 tracks for 400 miles, that's still the same as one track for 401 miles as all cars need to go through there.

5. Ahh, perfect. Now I understand. Not really sure why the book would ask me to change the application of the algorithm so much right out of the blue. Although this book is meant to be used in the classroom, rather than as a standalone book. So I guess it assumes I am using it in conjunction with someone who knows what they are doing :P

Again, many thanks