**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**.

That is, not only the shortest path is to be determined, but also the second shortest, the third shortes, and so up to the K-th shortest path.

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

- The K Shortest Disjoint Paths Problem:
- Arc-Disjoint Paths Problem;
- Node-Disjoint Paths Problem.

- The K Shortest Elementary Paths Problem;
- 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).

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

**Click here**
** for a paper ** with a new algorithm

**Bibliography: **

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

**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...

Crawl to