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