Ranked Shortest Path

Jump to bottom Edit New page

Andrey Vernigora edited this page Feb 2, 2019 · 3 revisions

Ranked Shortest Path Algorithm

This is a variation of the Shortest Path algorithm where not only the first one, but k-th shortest paths are returned

The Hoffman-Pavlet algorithm provides an implementation this problem for directed weight graph with positive weights.

IBidirectionalGraph<TVertex, TEdge> g = ...;
Func<TEdge, double> edgeWeights = ...;
TVertex source = ...;
TVertex target = ...;
int pathCount = 5;

foreach(IEnumerable<TEdge> path in g.RankedShortestPathHoffman(g, edgeWeights, source, target, 5))
    ...