Shortest path alogrithm

Topics: algorithm, graph
Sep 24, 2009 at 6:07 AM


I am really new to the field of graphs.  

I need to find the shortest distance between two places (nodes and edges magnitude is in 1000s).
The graph is undirectional. I mean going from A-B, B-A is similar and acceptable. So i dont want to create two edges i.e AB and BA.
I need to find the shortest distnace and the path for a pair of source and target.

Please provide some code to fulfill my requirement and suggest whether to choose AdjacencyGraph or IVertexAndEdgeListGraph.

Please provide any additional information which you may be helpful in this regard.






Sep 25, 2009 at 5:20 AM

Somebody help!!!!

Sep 25, 2009 at 6:57 AM

Use UndirectedShortestPath and the method AlgorithmExtensions.ShortestPathsDijkstra. This method will return a delegate that you can query for paths.

Sep 25, 2009 at 10:07 AM
Edited Sep 25, 2009 at 10:09 AM

Hi Sir

Please excuse my lack of knowledge. I was able to create Adjacency Graph as a working example was available on forum and was able to find the shortest distance between two place. but this graph is a directed one. I could find distance AB but not BA. Following is the code I used:

AdjacencyGraph<string, Edge<string>> graph = new AdjacencyGraph<string, Edge<string>>(true);
            // Add some cities to the graph
            // Create the streets (<string> -> the edge is identified by a string value)
            Edge<string> a_b = new Edge<string>("A", "B");
           // Add the streets

            // Define some lengths to the streets
            Dictionary<Edge<string>, double> edgeCost = new Dictionary<Edge<string>, double>(graph.EdgeCount);           

            edgeCost.Add(a_b, 4);
            DijkstraShortestPathAlgorithm<string, Edge<string>> dijkstra = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph, AlgorithmExtensions.GetIndexer<Edge<string>, double>(edgeCost));

            // Attach a Vertex Predecessor Recorder Observer to give us the paths
            QuickGraph.Algorithms.Observers.VertexPredecessorRecorderObserver<string, Edge<string>> predecessorObserver = new QuickGraph.Algorithms.Observers.VertexPredecessorRecorderObserver<string, Edge<string>>();

            // attach a distance observer to give us the shortest path distances
            VertexDistanceRecorderObserver<string, Edge<string>> distObserver = new VertexDistanceRecorderObserver<string, Edge<string>>(AlgorithmExtensions.GetIndexer<Edge<string>, double>(edgeCost));

            // Run the algorithm with A set to be the source
            label1.Text = "Shortest distance: ";
            label1.Text +=  distObserver.Distances["B"] + "\n";
            IEnumerable<Edge<string>> path;
          if(predecessorObserver.TryGetPath("B", out path))
              foreach (var u in path)
                  label1.Text += u +"\n" ;
I guess need to use IVertexAndEdgeListGraph for creating a undirected graph, but I could not find a working code for it. Else, I can opt to create duplicate 2 edges for edge as in both AB and BA, but that affect the perofrmace as the edges will be twice.
Please provide some code/pseudocode to create IVertexAndEdgeListGraph and add vertices and edges to it.
I really need it urgently...Please help



Sep 28, 2009 at 2:55 PM

Hello, if you want to use undirected graph you can do as follow :

var distances = new Dictionary<Edge<string>, double>();
var graphU = new UndirectedGraph<string, Edge<string>>();
var edge12 = new Edge<string>("1", "2");

var dijkstra = new UndirectedDijkstraShortestPathAlgorithm<string, Edge<string>>(graphU, AlgorithmExtensions.GetIndexer<Edge<string>, double>(distances));
var predecessorObserver = new UndirectedVertexPredecessorRecorderObserver<string, Edge<string>>();

foreach (var z in predecessorObserver.VertexPredecessors)
 Console.WriteLine("key:{0} value:{1}",z.Key,z.Value);

Sep 29, 2009 at 6:59 AM

Thank you very much.