Dijkstra Shortest Path Working Example

Topics: algorithm
Feb 27, 2009 at 11:57 AM

Hello, I am using QuickGraph for .Net2.0  and can not find the shortest path cause i get a compiling error (at the bolded line):
Something like "cannot convert argument 2 from Generic.Dictionary<... to QuickGraph.Func...
After searching around i found the following:
From: pelikhan
Dijkstra now takes a delegate that maps a TEdge to a double (i.e. map from edges to their cost). Implicitely, this was done by calling the indexer of the dictionary. Simply pass the following in your case: e => edgeCost[e]
I can not interpret the answer! Can I use this term directly in c# with .Net2.0?
I am currently not very familiar with the new .net features like generics and perhaps the syntax e=>....
Can someone pleeeeeaaaaseee help me to find the shortest path from "A" to "B" (there are some more commandos missing like observer,...)?
Below the code i found in the discussion forum:

AdjacencyGraph<string, Edge<string>> graph = new AdjacencyGraph<string, Edge<string>>(true);
// Add some vertices to the graph
graph.AddVertex("A");
graph.AddVertex("B");
// Create the edges
Edge<string> a_b = new Edge<string>("A", "B");
// Add the edges
graph.AddEdge(a_b);
// Define some weights to the edges
Dictionary<Edge<string>, double> edgeCost = new Dictionary<Edge<string>, double>(graph.EdgeCount);
edgeCost.Add(a_b, 4);
// We want to use Dijkstra on this graph
DijkstraShortestPathAlgorithm<string, Edge<string>> dijkstra = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph, edgeCost);


THANK YOU!

Stephan

Coordinator
Feb 27, 2009 at 7:42 PM
You need to pass a delegate to the constructor. In this case, the indexer of the dictionary edgeCount. Since the indexer is not really accessible from C#, you can use the AlgorithmExtensions.GetIndexer method:

using QuickGraph.Algorithms;
var dijkstra = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph,  edgeCost.GetIndexer());
Mar 2, 2009 at 8:26 AM

Thanks! Now it works! My complete example for other guys:    

AdjacencyGraph<string, Edge<string>> graph = new AdjacencyGraph<string, Edge<string>>(true);

            // Add some cities to the graph
            graph.AddVertex("A");
            graph.AddVertex("B");
            graph.AddVertex("C");
            graph.AddVertex("D");
            graph.AddVertex("E");
            graph.AddVertex("F");
            graph.AddVertex("G");
            graph.AddVertex("H");
            graph.AddVertex("I");
            graph.AddVertex("J");

            // Create the streets (<string> -> the edge is identified by a string value)
            Edge<string> a_e = new Edge<string>"A", "E");
            Edge<string> e_f = new Edge<string>("E", "F");
            Edge<string> f_g = new Edge<string>("F", "G");
            Edge<string> g_h = new Edge<string>("G", "H");

            // Add the streets
            graph.AddEdge(a_e);
            graph.AddEdge(e_f);
            graph.AddEdge(f_g);
            graph.AddEdge(g_h);

            // Define some lengths to the streets
            Dictionary<Edge<string>, double> edgeCost = new Dictionary<Edge<string>, double>(graph.EdgeCount);
            edgeCost.Add(a_e, 1);
            edgeCost.Add(e_f, 1);
            edgeCost.Add(f_g, 1);
            edgeCost.Add(g_h, 1);
    
            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>>();
            predecessorObserver.Attach(dijkstra);

            // 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));
            distObserver.Attach(dijkstra);

            // Run the algorithm with A set to be the source
            dijkstra.Compute("A");

            foreach (KeyValuePair<string, Edge<string>> kvp in predecessorObserver.VertexPredecessors)
                Console.WriteLine("If you want to get to {0} you have to enter through the in edge {1}", kvp.Key, kvp.Value);

            foreach (KeyValuePair<string, double> kvp in distObserver.Distances)
                Console.WriteLine("Distance from root to node {0} is {1}", kvp.Key, kvp.Value);

            // Remember to detach the observers
            predecessorObserver.Detach(dijkstra);
            distObserver.Detach(dijkstra);

Coordinator
Mar 2, 2009 at 4:41 PM
You can use the AlgorithmExtensions.ShortestPathsDijkstra method to do this kind of computation. It wraps the creation of a recorder/algorithm, etc...