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

[ForumAccount]

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