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))
    ...

Last edited Jan 4, 2009 at 10:03 PM by pelikhan, version 4

Comments

sw_lasse Nov 2, 2012 at 7:22 AM 
Does anybody know what the computational complexity of this implementation is? I have tried looking in the paper, but as far as I can tell, that is not stated explicitly. Thanks in advance.

simmotech Jun 16, 2011 at 12:27 PM 
Hoffman-Pavley is spelt incorrectly on this page.