Results 1 to 2 of 2

Math Help - dijkstra's algorithm

  1. #1
    Newbie
    Joined
    Dec 2007
    From
    UK
    Posts
    23

    Question dijkstra's algorithm

    Using the dijkstra's algorithm find the shortest path from node c to node f, shown in the attached graph.

    Any help would be greatly appreciated!
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jan 2008
    Posts
    3

    Dijkstra's Algorithm

    Ok, so first, here's the steps that you follow in Dijkstra's algorithm.

    First, identify your starting node. In your example, this is node c.
    Next, identify all nodes that are "reachable" from node c. These are nodes b and d.
    Choose the node with the "least expensive" edge. In this case, it is (c,d), which has a "cost" of 4.

    Now, nodes c and d are both in the set of nodes that have permanent distances.

    Your next goal is to look for nodes that are reachable from any node that has already has a permanent distance. Here is one of the main keys to the algorithm - if you're going from a node that is already in the permanent set to a node that is not (let's call them i and j, respectively), the total distance traveled is (permanent distance of i + distance from i to j). You need to remember to update the distances at each step. In this case, the distance from c to b is still 6, while the distance from d to a is (4+10=14) and the distance from d to e is (4+1=5). The cheapest distance of these sets is 5, so add e to the permanent set.

    This process repeats itself. I really recommend going to this website
    Dijkstra's Shortest Path Algorithm
    and using the applet there to see how the rest of the steps work. You just draw in your graph, and it will step through it in a very understandable way. I've also included a file with the solution to this problem.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: January 2nd 2012, 08:58 PM
  2. [SOLVED] Graphs, Dijkstra's algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 11th 2011, 04:20 PM
  3. Understanding Dijkstra
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 7th 2010, 01:05 PM
  4. Replies: 4
    Last Post: May 10th 2009, 10:29 AM
  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