K-th Shortest Path Problem

Version: Draft 1.0

Last Update: December, 1995

Subject Index:

One Liner: Ranking shortest paths by non decreasing order of their distances

Body:

The reader is assumed to know some basic concepts and notation about the optimal path problem.

The following classes of the K-th Shortest Path Problem are usually considered:

1. The K Shortest Disjoint Paths Problem:
   1. Arc-Disjoint Paths Problem;
   2. Node-Disjoint Paths Problem.
2. The K Shortest Elementary Paths Problem;
3. The General K Shortest Paths Problem.

Definition: Two (or more) paths are arc-disjoint if they have no common arcs; two (or more) paths are node-disjoint if they have no common intermediate nodes.

From the last definition it is immediate that node-disjoint paths are also arc-disjoint paths.

Let us consider the K Shortest Arc-Disjoint Paths Problem where it is intended to determine a set of arc-disjoint paths.
This problem is equivalent to following minimal cost flow problem:

That is, we intend to determine a feasible flow, valued K, from the initial node to terminal node, and such that the total cost is minimal. The flow in each arc can not exceed the unity.
Obviously, if such a flow does not exists, the same can be concluded about the K disjoint paths.
The optimal solution of the minimal cost flow problem does not show us which is the k-th shortest disjoint path. So, if we are interested to know which is each one of the k-th shortest disjoint paths, we have to construct a new network, whose set of arcs is the set of arcs for which the flow is one. (The set of nodes is trivially determined). To determine the shortest disjoint path, the second disjoint shortest, the third disjoint shortest, and so up to the K-th shortest disjoint path, we have to execute K times the following two steps (begining with the new network):
- Compute a shortest path in the resulting network;
- Remove its arcs (it results a new network).
The algorithm is exemplified with the network on the left, where the initial node (s) is 1, the terminal node (t) is 4 and the number close to each arc represents its cost (or distance...).
Let us assume that we intend to determine the two disjoint shortest paths, from s to t.
According the algorithm, we only have to determine a minimal cost flow, valued 2, from s to t, in the given network. In the optimal solution for this problem, the flow is 1 in each arc but (2,4) where is zero. So, the resulting network is that one on the right, where the shortest path from 1 to 4 is {1, (1,2), 2, (2,4), 4}. Once this path is removed, we get the second shortest disjoint path - {1, (1,3), 3, (3,4), 4}.
Note that the shortest path in the original network - {1, (1,2), 2, (2,3), 3, (3,4), 4} - is not one of the two shortest disjoint paths. So, it will results a wrong conclusion if we try to solve the problem executing K times the following two steps, (begining with the given network): compute a shortest path and remove its arcs from the network.

Let us consider now the K Shortest Node-Disjoint Paths Problem where it is intended to determine a set of node-disjoint paths.
This problem is easily transformed into a K Shortest Arc-Disjoint Paths Problem. So , let us consider some node x, to which is allowed to belong to a single path; let us split node x into two nodes, x' and x", linked by the zero cost arc (x',x"), and keeping the arc distances, let us change all the arcs (i,x) to arcs (i,x') and all the arcs (x,j) to arcs (x",j). We only need to determine the K Shortest Arc-Disjoint Paths in the resulting network, to determine the K Shortest Node-Disjoint Paths in the original one.
As an example, let us consider the network on the left where we intend to determine the three shortest paths from s=1 to t=5, in such a way that no more than one path passes throughout node 3; the figure on right represents the transformed network for this problem.
If we bound to one the flow capacity of all the arcs and we send three units of flow from node 1 to node 5 minimizing the cost, we will get one unit of flow in all the arcs but (3",4) and (3",2), where the flow is zero. That is, an optimal solution for the problem would be the paths {1, (1,2), 2, (2,5), 5}, {1, (1,3), 3, (3,5), 5} and {1, (1,4), 4, (4,5), 5}, all of them with cost 10.

Bibliography: Detailed information can be obtained about the K disjoint Paths Problem on the paper:
"Disjoint Paths in a Network", by J.W.Suurballe (Networks, 4: 125-145, 1974).

Ranking Elementary Paths

Definition: A path is said to be an elementary path if no node is repeated.

Click here for a paper with a new algorithm

The General K-th Shortest Path Problem

Bibliography:

• An excelent and complete biblyography, due to David Eppstein, is available on line.

This introduction to the "K-th Shortest Path Problem" is a constantly envolving document and feedback is appreciated.

Contributer: Ernesto Martins

Referenced by:

Refers to: David Eppstein Home Page and Algorithms for Computing the K Shortest Paths by Víctor Jiménez and Andrés Marzal

Status: In construction...