Dijkstra Shortest Distance Example - KeRNeLith/QuikGraph GitHub Wiki

Dijkstra Shortest Path Distance Example

Dijkstra extension methods

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

using QuikGraph;
using QuikGraph.Algorithms;

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

// Compute shortest paths
TryFunc<TVertex, IEnumerable<TEdge>> tryGetPaths = graph.ShortestPathsDijkstra(edgeCost, root);

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

Advanced use

For more advanced usages you can fallback to use the version of the algorithm that is not hidden behind an extension method.

This example sets up a Dijkstra shortest path algorithm and computes the distance of the vertices in the graph.

Func<Edge<string>, double> edgeCost = edge => 1; // Constant cost
// We want to use Dijkstra on this graph
var dijkstra = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph, edgeCost);

Using a predecessor recorder to build the shortest path tree

Algorithms raise a number of events that observers 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<string, Edge<string>>();
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 (string vertex in graph.Vertices)
{
    double distance = 0;
    TVertex v = vertex;
    while (predecessors.VertexPredecessors.TryGetValue(v, out TEdge predecessor))
    {
        distance += edgeCost(predecessor);
        v = predecessor.Source;
    }
    Console.WriteLine($"A -> {v}: {distance}");
}

Using a dictionary for edge costs

Because the algorithm takes a delegate as the edge cost, one cannot simply pass a dictionary. QuikGraph provides an helper method, GetIndexer, to make the conversion

Dictionary<TEdge, double> edgeCostDictionary = ...;
Func<TEdge, double> edgeCost = AlgorithmExtensions.GetIndexer(edgeCostDictionary);
...
⚠️ **GitHub.com Fallback** ⚠️