Shortest Path

This single source shorteset 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, 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 citiesFunc<Edge<int>,double>cityDistances= ...;// a delegate that gives the distance between citiesintsourceCity=0;// starting cityinttargetCity=0;// ending city// vis can create all the shortest path in the graph// and returns a delegate that can be used to retreive the graphsTryGetFunc<int,IEnumerable<int>>tryGetPath=cities.ShortestPathsDijkstra(cityDistances,sourceCity);// enumerating path to targetCity, if anyIEnumerable<Edge<int>>path;if(tryGetPath(targetCity,outpath))foreach(vareinpath)Console.WriteLine(e);

Full example

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

// creating the algorithm instancevardijkstra=newDijkstraShortestPathAlgorithm<int,Edge<int>>(cities,cityDistances);// creating the observervarvis=newVertexPredecessorRecorderObserver<int,Edge<int>>();// compute and record shortest pathsusing(ObserverScope.Create(dijkstra,vis))dijkstra.Compute(sourceCity);// vis can create all the shortest path in the graphforeach(vareinvis.Path(targetCity))Console.WriteLine(e);