Dijkstra Shortest Path Distance Example

Dijkstra extension methods

The AlgorithmExtensions class contains several helper methods to execute the algorithm on a given graph.
using QuickGraph;
using QuickGraph.Algorithms;

IVertexAndEdgeListGraph<TVertex, TEdge> graph = ...;
Func<TEdge, double> edgeCost = e => 1; // constant cost
TVertex root = ...;

// compute shortest paths
TryFunc<TVertex, TEdge> tryGetPaths = graph.ShortestPathDijkstra(edgeCost, root);

// query path for given vertices
TVertex target = ...;
IEnumerable<TEdge> path;
if (tryGetPaths(target, out path))
    foreach(var edge in path)
        Console.WriteLine(edge);

Advanced use

This example sets up a Dijkstra shortest path algorithm and computes the distance of the vertices in the graph.
Func<TEdge, double> edgeCost = e => 1; // constant cost
// We want to use Dijkstra on this graph
var dijkstra = new DijkstraShortestPathAlgorithm<TEdge, TEdge>(graph, edgeCost);

Using a predecessor recorder to build the shortest path tree

Algorithms raise a number of events that observes can leverage to build solutions. For example, attaching a predecessor recorder
to the Dijkstra algorithm will let us build a predecessor tree. This tree is later used to build shortest paths.
// Attach a Vertex Predecessor Recorder Observer to give us the paths
var predecessors = new VertexPredecessorRecorderObserver<TVertex, TEdge>();
using (predecessors.Attach(dijkstra))
    // Run the algorithm with A set to be the source
    dijkstra.Compute("A");

The predecessors instance now contains a dictionary of distance from each vertex to the source:
foreach (var v in graph.Vertices) {
    double distance = 0;
    TVertex vertex = v;
    TEdge predecessor;
     while (predecessors.VertexPredecessors.TryGetValue(vertex, out predecessor)) {
          distance += edgeCost[predecessor];
          vertex = predecessor.Source;
     }
     Console.WriteLine("A -> {0}: {1}", v, distance);
}
Using a dictionary for edge costs
Because the algorithm take a delegate as the edge cost, one cannot simply pass a dictionary. QuickGraph provides a helper method, GetIndexer, to make the conversion:
Dictionary<TEdge, double> edgeCostDictionary = ...
Func<TEdge,double> edgeCost = AlgorithmExtensions.GetIndexer(edgeCostDictionary);
...

Last edited Apr 26, 2009 at 8:34 AM by pelikhan, version 10

Comments

aphillips801 Dec 12, 2012 at 6:56 AM 
Another typo:

TryFunc<TVertex, TEdge> tryGetPaths = graph.ShortestPathDijkstra(edgeCost, root);

should be:

TryFunc<TVertex, TEdge> tryGetPaths = graph.ShortestPathsDijkstra(edgeCost, root);

ALSO...

I finally got some code to compile but when run I get a run-time error because Comparer.Compare() is being used to compare vertices. My vertices are of type PointF which does not implement IComparable. My question is why do the vertices need to be ordered? I could imagine why they would need IEquatable but why IComparable?

naman Feb 9, 2012 at 1:31 AM 
Typo:

var dijkstra = new DijkstraShortestPathAlgorithm<TEdge, TEdge>...

should be

var dijkstra = new DijkstraShortestPathAlgorithm<TVertex, TEdge>