An algorithm to find the shortest paths from node to node is presented.

In a digraph , we derive a subgraph which is the shortest path tree (spanning tree) from every node to node . Then any edge not in is called the sidetrack edges. A path from to , not necessarily the shortest path, can be uniquely identified by the set of sidetracked edges it contains: Given a set of sidetracked edges, a path is derived as follows: We begin from node , traverse along the path in . Whenever a sidetracked edge is encountered, we traverse it and switched to another branch, until node is reached.

For every edge , we define a quantity to denote the extra distance traversed by sidetracking to edge [note: the paper has this equation wrong]. Here, is the length of , and is the shortest distance between nodes and according to tree . If edge is in , . Then, the path joining to has the distance of

The focus of this paper is to derive the complexity for enumeration of the k paths of minimum distance, by using a heap data structure.

Bibliographic data

@article{
   title = "Finding the k shortest paths",
   author = "David Eppstein",
   journal = "SIAM J. Computing",
   volume = "28",
   number = "2",
   pages = "652--673",
   year = "1998",
}