[.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:

<?xml version="1.0" encoding="utf-8"?>
<root vertexCount="10" edgeCount="14">
  <vertex>
    <key>Edmonton</key>
  </vertex>
  <vertex>
    <key>Red Deer</key>
  </vertex>
  <vertex>
    <key>Calgary</key>
  </vertex>
  <vertex>
    <key>Lethbridge</key>
  </vertex>
  <vertex>
    <key>Great Falls</key>
  </vertex>
  <vertex>
    <key>Kelowna</key>
  </vertex>
  <vertex>
    <key>Kamloops</key>
  </vertex>
  <vertex>
    <key>Medicine Hat</key>
  </vertex>
  <vertex>
    <key>Regina</key>
  </vertex>
  <vertex>
    <key>Saskatoon</key>
  </vertex>
  <edge>
    <firstKey>Edmonton</firstKey>
    <secondKey>Red Deer</secondKey>
    <distance>157</distance>
  </edge>
  <edge>
    <firstKey>Red Deer</firstKey>
    <secondKey>Calgary</secondKey>
    <distance>146</distance>
  </edge>
  <edge>
    <firstKey>Edmonton</firstKey>
    <secondKey>Kamloops</secondKey>
    <distance>805</distance>
  </edge>
  <edge>
    <firstKey>Kamloops</firstKey>
    <secondKey>Kelowna</secondKey>
    <distance>168</distance>
  </edge>
  <edge>
    <firstKey>Great Falls</firstKey>
    <secondKey>Kelowna</secondKey>
    <distance>993</distance>
  </edge>
  <edge>
    <firstKey>Great Falls</firstKey>
    <secondKey>Regina</secondKey>
    <distance>805</distance>
  </edge>
  <edge>
    <firstKey>Medicine Hat</firstKey>
    <secondKey>Regina</secondKey>
    <distance>466</distance>
  </edge>
  <edge>
    <firstKey>Medicine Hat</firstKey>
    <secondKey>Lethbridge</secondKey>
    <distance>170</distance>
  </edge>
  <edge>
    <firstKey>Calgary</firstKey>
    <secondKey>Lethbridge</secondKey>
    <distance>211</distance>
  </edge>
  <edge>
    <firstKey>Calgary</firstKey>
    <secondKey>Medicine Hat</secondKey>
    <distance>294</distance>
  </edge>
  <edge>
    <firstKey>Edmonton</firstKey>
    <secondKey>Saskatoon</secondKey>
    <distance>526</distance>
  </edge>
  <edge>
    <firstKey>Regina</firstKey>
    <secondKey>Saskatoon</secondKey>
    <distance>257</distance>
  </edge>
  <edge>
    <firstKey>Lethbridge</firstKey>
    <secondKey>Great Falls</secondKey>
    <distance>302</distance>
  </edge>
  <edge>
    <firstKey>Calgary</firstKey>
    <secondKey>Kamloops</secondKey>
    <distance>623</distance>
  </edge>
</root>

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

Quote:

---

Originally Posted by tharatp

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.

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)..

https://public.sn2.livefilestore.com...ail.jpg?psid=1

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

https://skydrive.live.com/?cid=08617...0F630E8729!348

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