An algorithm to find the $$k$$ shortest paths from node $$s$$ to node $$t$$ is presented.

In a digraph $$G$$, we derive a subgraph $$T$$ which is the shortest path tree (spanning tree) from every node to node $$t$$. Then any edge $$e$$ not in $$T$$ is called the sidetrack edges. A path from $$s$$ to $$t$$, 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 $$s$$, traverse along the path in $$T$$. Whenever a sidetracked edge is encountered, we traverse it and switched to another branch, until node $$t$$ is reached.

For every edge $$e$$, we define a quantity $$\delta(e)=\ell(e)+d(e_{\textrm{tail}},t)-d(e_{\textrm{head}},t)$$ to denote the extra distance traversed by sidetracking to edge $$e$$ [note: the paper has this equation wrong]. Here, $$\ell(e)$$ is the length of $$e$$, and $$d(a,b)$$ is the shortest distance between nodes $$a$$ and $$b$$ according to tree $$T$$. If edge $$e$$ is in $$T$$, $$\delta(e)=0$$. Then, the path $$p$$ joining $$s$$ to $$t$$ has the distance of $$\ell(p)=d(s,t)+\sum_{e\in p}\delta(e)$$

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",
}