Shortest Path

Shortest Path

This single source shortest path can be expressed as follows: given a weighted directed graph, find the minimum path between a vertex u and any other vertex v.

Depending on the properties of the weights and the graph, different algorithms can be applied:

• positive weights and graph is a Directed Acyclic Graph: DagShortestPathAlgorithm
• positive weights: DijsktraShortestPathAlgorithm
• positive weights, with heuristics: AStartShortestPathAlgorithm
• positive or negative weights: BellmanFordShortestPathAlgorithm

Quick example

The AlgorithmExtensions contains extension methods to compute the shortest path without the ugly details.

IVertexAndEdgeListGraph<int, Edge<int>> cities = ...; // A graph of cities
Func<Edge<int>, double> cityDistances = ...; // A delegate that gives the distance between cities

int sourceCity = 0; // Starting city
int targetCity = 0; // Ending city

// Returns a delegate that can be used to retrieve the paths
TryFunc<int, IEnumerable<int>> tryGetPath = cities.ShortestPathsDijkstra(cityDistances, sourceCity);
// Enumerating path to targetCity, if any
if (tryGetPath(targetCity, out IEnumerable<Edge<int>> path))
{
    foreach (Edge<int> edge in path)
    {
        Console.WriteLine(edge);
    }
}

Full example

This sample shows how to compute the shortest path between different cities.

// Creating the algorithm instance
var dijkstra = new DijkstraShortestPathAlgorithm<int, Edge<int>>(cities, cityDistances);

// Creating the observer
var vis = new VertexPredecessorRecorderObserver<int, Edge<int>>();

// Compute and record shortest paths
using (vis.Attach(dijkstra))
{
    dijkstra.Compute(sourceCity);
}

// vis can create all the shortest path in the graph
if (vis.TryGetPath(targetCity, out IEnumerable<Edge<int>> path))
{
    foreach(Edge<int> edge in path)
    {
        Console.WriteLine(edge);
    }
}