A Multi Label Algorithm for K Shortest Paths Problem

Abstract

The paper presents an algorithm for computing k shortest walks or k shortest paths in a directed graph G (V, A). The proposed algorithm can be applied for solving the k shortest paths problem in an undirected graph G (V, E), too, by transforming the graph G (V,E) to the digraph G(V, A) where the arc set A contains a couple of arcs (u,v), (v,u) for every edge {u,v} E.