P79: Enumeration of $k$ shortest paths in a graph

P79: Enumeration of $k$ shortest paths in a graph

Input:

A graph $G = (V, E)$.

Output:

$k$ shortest paths in $G$.

Complexity:

$O(k|V|c(|V|))$ total time.

Comment:

(?) $c(n)$ is the time complexity to find an optimal solution to a problem with $n$ (0, 1) variables.

Reference:

[Lawler1972] (Bibtex)