Results 1 to 6 of 6

Thread: [.NET 3.5+] Dijkstra's Algorithm (Shortest Path Algorithm)

  1. #1

    Thread Starter
    Master Of Orion ForumAccount's Avatar
    Join Date
    Jan 2009
    Location
    Canada
    Posts
    2,802

    [.NET 3.5+] Dijkstra's Algorithm (Shortest Path Algorithm)

    The following is a OO implementation of Dijkstra's algorithm with a basic UI as well.

    Everything is fully documented so I don't really need to go into details. See the attachments which shows the algorithm determining the fastest route between cities. The UI isn't great but helps provide a quick way of making a Graph. Implementation is contained in the namespace System.Algorithms.Dijkstra.

    Underline = It's a member of the object.
    Bold = It's a type in the namespace.

    Graph:
    • Graph object can Save itself as Xml to a file, and Load from a file as well.
    • AddVertex - Creates, and adds a Vertex to the Graph.
    • AddEdge - Creates, and adds an Edge to the Graph.
    • Calculate - Runs the algorithm on the Graph.
    • GetPath - Returns the a string that represents the order to take for the shortest path. See the second line of the MessageBox screenshot.
    • GetDistance - Returns the calculated total distance between the two specified verticies. See the third line of the MessageBox screenshot.
    • GetVerticies - Returns an array of Vertex objects that form the shortest path.
    • The other members have documentation so you understand what they do as well.


    Vertex:
    • Can only be created within the Graph object, keeps it clean.
    • Vertex is basically a location in the Graph.
    • Key - The string identifier for the Vertex.
    • Neighbors - Gets the verticies that connect with the instance via an Edge.
    • Distance - Gets the distance from the initial node. Once the Graph has been calculated this member is populated.


    Edge:
    • Can only be created within the Graph object, keeps it clean.
    • Edge is basically a definition of distance between two verticies.
    • Distance - The distance between the two verticies of the Edge object. Not to be confused with the Distance member in the Vertex object.


    Attachments:
    • Graph = Map
    • Vertex = City
    • Edge = Road


    Xml (From Attachments):

    xml Code:
    1. <?xml version="1.0" encoding="utf-8"?>
    2. <root vertexCount="10" edgeCount="14">
    3.   <vertex>
    4.     <key>Edmonton</key>
    5.   </vertex>
    6.   <vertex>
    7.     <key>Red Deer</key>
    8.   </vertex>
    9.   <vertex>
    10.     <key>Calgary</key>
    11.   </vertex>
    12.   <vertex>
    13.     <key>Lethbridge</key>
    14.   </vertex>
    15.   <vertex>
    16.     <key>Great Falls</key>
    17.   </vertex>
    18.   <vertex>
    19.     <key>Kelowna</key>
    20.   </vertex>
    21.   <vertex>
    22.     <key>Kamloops</key>
    23.   </vertex>
    24.   <vertex>
    25.     <key>Medicine Hat</key>
    26.   </vertex>
    27.   <vertex>
    28.     <key>Regina</key>
    29.   </vertex>
    30.   <vertex>
    31.     <key>Saskatoon</key>
    32.   </vertex>
    33.   <edge>
    34.     <firstKey>Edmonton</firstKey>
    35.     <secondKey>Red Deer</secondKey>
    36.     <distance>157</distance>
    37.   </edge>
    38.   <edge>
    39.     <firstKey>Red Deer</firstKey>
    40.     <secondKey>Calgary</secondKey>
    41.     <distance>146</distance>
    42.   </edge>
    43.   <edge>
    44.     <firstKey>Edmonton</firstKey>
    45.     <secondKey>Kamloops</secondKey>
    46.     <distance>805</distance>
    47.   </edge>
    48.   <edge>
    49.     <firstKey>Kamloops</firstKey>
    50.     <secondKey>Kelowna</secondKey>
    51.     <distance>168</distance>
    52.   </edge>
    53.   <edge>
    54.     <firstKey>Great Falls</firstKey>
    55.     <secondKey>Kelowna</secondKey>
    56.     <distance>993</distance>
    57.   </edge>
    58.   <edge>
    59.     <firstKey>Great Falls</firstKey>
    60.     <secondKey>Regina</secondKey>
    61.     <distance>805</distance>
    62.   </edge>
    63.   <edge>
    64.     <firstKey>Medicine Hat</firstKey>
    65.     <secondKey>Regina</secondKey>
    66.     <distance>466</distance>
    67.   </edge>
    68.   <edge>
    69.     <firstKey>Medicine Hat</firstKey>
    70.     <secondKey>Lethbridge</secondKey>
    71.     <distance>170</distance>
    72.   </edge>
    73.   <edge>
    74.     <firstKey>Calgary</firstKey>
    75.     <secondKey>Lethbridge</secondKey>
    76.     <distance>211</distance>
    77.   </edge>
    78.   <edge>
    79.     <firstKey>Calgary</firstKey>
    80.     <secondKey>Medicine Hat</secondKey>
    81.     <distance>294</distance>
    82.   </edge>
    83.   <edge>
    84.     <firstKey>Edmonton</firstKey>
    85.     <secondKey>Saskatoon</secondKey>
    86.     <distance>526</distance>
    87.   </edge>
    88.   <edge>
    89.     <firstKey>Regina</firstKey>
    90.     <secondKey>Saskatoon</secondKey>
    91.     <distance>257</distance>
    92.   </edge>
    93.   <edge>
    94.     <firstKey>Lethbridge</firstKey>
    95.     <secondKey>Great Falls</secondKey>
    96.     <distance>302</distance>
    97.   </edge>
    98.   <edge>
    99.     <firstKey>Calgary</firstKey>
    100.     <secondKey>Kamloops</secondKey>
    101.     <distance>623</distance>
    102.   </edge>
    103. </root>
    Attached Images Attached Images     
    Attached Files Attached Files

  2. #2
    New Member
    Join Date
    Mar 2011
    Posts
    1

    Re: [.NET 3.5+] Dijkstra's Algorithm (Shortest Path Algorithm)

    Dear sir,

    Thank u for such a thread in VB. But i request for some clarification on the output. ie., can we visualise the shortest path followed in each run on this image?Actually i have an Arcmap shapefile for road network of around 500 nodes. can i use the same format? if not, what can i do for a better result?Can i get documentation on the procedure?


    with regards,

    Thara T.P

  3. #3

    Thread Starter
    Master Of Orion ForumAccount's Avatar
    Join Date
    Jan 2009
    Location
    Canada
    Posts
    2,802

    Re: [.NET 3.5+] Dijkstra's Algorithm (Shortest Path Algorithm)

    Quote Originally Posted by tharatp View Post
    Dear sir,

    Thank u for such a thread in VB. But i request for some clarification on the output. ie., can we visualise the shortest path followed in each run on this image?Actually i have an Arcmap shapefile for road network of around 500 nodes. can i use the same format? if not, what can i do for a better result?Can i get documentation on the procedure?


    with regards,

    Thara T.P
    You would have to create your own code for a visual representation of the shortest path. This class will just tell you what it is.

  4. #4
    New Member
    Join Date
    Feb 2012
    Posts
    2

    Re: [.NET 3.5+] Dijkstra's Algorithm (Shortest Path Algorithm)

    Hi, very cool program!

    I tried it with a small example and it did not work correctly though.
    Take this Graph:
    i j d(i,j)
    1 2 100
    1 3 30
    2 3 20
    3 4 10
    3 5 60
    4 2 15
    4 5 50

    When you try to calculate the shortest path between 1 and 2, it should go (1)-(3)-(4)-(2), distance = 30+10+15 = 55.

    This programs says (1)-(3)-(2), distance = 50 !
    There is no edge (3)-(2)..


  5. #5
    New Member
    Join Date
    Feb 2012
    Posts
    2

    Re: [.NET 3.5+] Dijkstra's Algorithm (Shortest Path Algorithm)

    Ah, apparently your code is for undirected graphs, I see.
    I have changed the GetNeighbors method and the item property of the edgecollection and I think it works now


  6. #6

    Thread Starter
    Master Of Orion ForumAccount's Avatar
    Join Date
    Jan 2009
    Location
    Canada
    Posts
    2,802

    Re: [.NET 3.5+] Dijkstra's Algorithm (Shortest Path Algorithm)

    You are correct, in this application, an edge of 2 -> 3 is the same as 3 -> 2.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width