Shortest path alogrithm

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

Hi

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.

Regards
Atul

 

 

 

 

Sep 25, 2009 at 6:20 AM

Somebody help!!!!

Coordinator
Sep 25, 2009 at 7: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 11:07 AM
Edited Sep 25, 2009 at 11: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
            graph.AddVertex("A");
            
            // Create the streets (<string> -> the edge is identified by a string value)
            
            Edge<string> a_b = new Edge<string>("A", "B");
           
           // Add the streets
           
            graph.AddEdge(a_b);           

            // 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>>();
            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");
                   
            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 3: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>>();
graphU.AddVertex("1");graphU.AddVertex("2");
var edge12 = new Edge<string>("1", "2");
graphU.AddEdge(edge12);
distances.Add(edge12,3);

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

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

Sep 29, 2009 at 7:59 AM

Thank you very much.