P58: Enumeration of the $k$ shortest paths in a directed graph

P58: Enumeration of the $k$ shortest paths in a directed graph

Input:

A directed graph $G = (V, E)$ and an integer $k$.

Output:

The $k$ smallest shortest paths in $G$.

Complexity:

$O(k|E|)$ total time

Comment:

Reference:

[Eppstein1998] (Bibtex)