5 Attachment(s)
[.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>
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
Re: [.NET 3.5+] Dijkstra's Algorithm (Shortest Path Algorithm)
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.
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)..
https://public.sn2.livefilestore.com...ail.jpg?psid=1
Re: [.NET 3.5+] Dijkstra's Algorithm (Shortest Path Algorithm)
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
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.