Results 1 to 4 of 4

Math Help - Understanding Dijkstra

  1. #1
    Newbie
    Joined
    Nov 2010
    Posts
    13

    Understanding Dijkstra

    Hey,
    I havnt done dijkstra for a while and im having trouble understanding the universities notes etc.

    For a very simple graph, nodes 1, 2, 3
    {1,2} = length 2
    {1, 3} = length 3
    {2, 3} = length 2

    Now, naturally, i'd have though Dijkstra's spanning tree starting from node 3 would be {2, 3} + {1,3} = 5

    However, via table:
    Nodes:
    1 2 3
    ---------------------------
    3 | 3 2 0 | Lowest is 2 so i highlight this. And write node 2 in next row
    2 | 2 2 | lowest is 2

    However this gives a spanning tree of {1,2}, {2, 3} = 4.

    And whilst this is lower, i'd have thought it'd be the other...

    What am i doing wrong? I have a feeling it's the table and i should be adding something to the values and checking each node, rather then selecting the lowest and taking the row it is in.
    Last edited by mr fantastic; November 7th 2010 at 11:30 AM. Reason: Title.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    In case this is still relevant... It has been some time since I studied the algorithm myself, and I don't know how to execute it via a table. However, first, it is not Dijkstra's, but Prim's algorithm that finds a minimal spanning tree. The goal of Dijkstra's algorithm is to mark each vertex with the shortest distance from the initial vertex. It is not clear to me how to recover a spanning tree from the order of visited vertices.

    In Dijkstra's algorithm, if you start with vertex 3, you mark vertex 2 with distance 2 and vertex 1 with distance 3, and you mark 3 as visited. Then you go to vertex 2, as having the least label, and consider its neighbor 1, but 1's label is already smaller than 2 + 2, so you leave it unchanged and mark 2 as visited. Then you go to 1, but since it has no unvisited neighbors, you mark it as visited and you are done. The shortest distance to 2 is 2 and to 1 is 3.

    In Prim's algorithm, you first add an edge {2, 3}. In the next step, you could add either {1, 2} or (1, 3}, but since the former is shorter, you add it and you are done.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2010
    Posts
    13
    Yeah, with the Dijsktra spanning tree, this was why i was getting so confused, because as far as i was concerned, Dijkstra shouldnt be producing a spanning tree! But the question still asked for one.

    This animation showed a spanning tree too

    Dijkstra's Algorithm Animated

    Thankyou for your reply
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    On second thought, I think that Dijsktra's algorithm can produce spanning trees with a bit more bookkeeping. Namely, suppose the current vertex is u and one of its unvisited neighbors is v. If the current label l(v) of v is greater than the label l(u) of u plus d(u,v), then we change v's label to l(u) + d(u,v). In addition, we should record that l(v) is achieved via u. At some later stage, when v is chosen as current because l(v) is the least among unvisited vertices, the edge (u,v) is added to the spanning tree.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: January 2nd 2012, 07:58 PM
  2. [SOLVED] Graphs, Dijkstra's algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 11th 2011, 03:20 PM
  3. Replies: 4
    Last Post: May 10th 2009, 09:29 AM
  4. dijkstra's algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 6th 2008, 11:16 AM
  5. LINEAR OPTIMIZATION PROBLEM (Dijkstra's algorithm)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 12th 2007, 06:45 PM

Search Tags


/mathhelpforum @mathhelpforum