Floyd Warshall All Path Shortest Path

Floyd Warshall All Path Shortest Path

The Floyd Warshall All Path Shortest Path finds all the shortest path in a weighted, directed graph. It can also be used to detect negative cycles.

var graph = ... ; // Some graph of TVertex, TEdge
Func<TEdge, double> weights = ... ; // a function that maps TEdge -> double
var fw = new FloydWarshallAllShortestPathAlgorithm<TVertex, TEdge>(graph, weights);

// Compute
fw.Compute();

// Get interesting paths
foreach(TVertex source in graph.Vertices)
{
    foreach(TVertex target in graph.Vertices)
    {
        if (fw.TryGetPath(source, target, out IEnumerable<TEdge> path)
        {
            foreach(TEdge edge in path)
            {
                Console.WriteLine(edge);
            }
        }
    }
}