Results 1 to 5 of 5

Math Help - How to modify Dijkstra's Algorithm to find the fastest path between 2 points...

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    3

    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?

    Thank you for your help.
    Attached Thumbnails Attached Thumbnails How to modify Dijkstra's Algorithm to find the fastest path between 2 points...-graph.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    May 2009
    From
    Tokyo, Japan
    Posts
    46
    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.
    Last edited by TiRune; May 9th 2009 at 08:29 AM. Reason: addition
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    Posts
    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. :/
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    May 2009
    From
    Tokyo, Japan
    Posts
    46
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2009
    Posts
    3
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Graphs, Dijkstra's algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 11th 2011, 04:20 PM
  2. Replies: 3
    Last Post: March 22nd 2010, 09:04 AM
  3. Fastest sorting algorithm
    Posted in the Discrete Math Forum
    Replies: 18
    Last Post: April 7th 2008, 09:31 PM
  4. dijkstra's algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 6th 2008, 12:16 PM
  5. LINEAR OPTIMIZATION PROBLEM (Dijkstra's algorithm)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 12th 2007, 07:45 PM

Search Tags


/mathhelpforum @mathhelpforum