Optimal Path Problems

Version: 1.0

Last Update: December, 1995

Subject Index:

One Liner: Optimal path problems

Body:

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

The paper The Optimal Path problem is on line for now.

General Overview

Under the general title Optimal Path Problems a very large class of network optimization problems are studied. In such problems a well defined sub-set P of paths between a given pair of nodes is considered and a sub-set Q of P has to be determined once paths in Q are prefered to any other path of P/Q, when some given criteria is considered.
network As an example, let us considerer the network in the figure on the left, where an integer distance is associated with each arc. Let us define the path distance as the sum of the distances associated with their arcs. For example, let us consider P as the set of paths with no repeated nodes (elementary paths) defined from node s=1 to node t=5. That is, P={A,B,C,D,E}, where A={1,(1,2),2,(2,5),5}, B={1,(1,2),2,(2,3),3,(3,5),5}, C={1,(1,3),3,(3,5),5}, D={1,(1,4),4,(4,3),3,(3,5),5} and E={1,(1,4),4,(4,5),5}. Denoting by d(X) the distance of path X, it results that d(A)=7+10=17, d(B)=7+5+12=24, d(C)=1+12=13, d(D)=32+9+12=53 and d(E)=32+8=40. Assuming that it is intended to determine a shortest path, i.e., a path with small distance, that path would be C.

In the example above, an exaustive search was used to solve the problem. However, in general such method is not suitable once the number of paths in P is very very large what would implies execution times out of the human mind, even if a very powerful computer were used. As so, we have to study methods to solve the problem in a reasonable execution time.

Let us assign to each node i of the network a label, i.e., a pair (pi(i),qsi(i)), where pi(i) is the distance of known shortest path in the set of paths from the initial node 1 to node i and qsi(i) is the predecessor node of i in that known shortest path. Of course, if no path is yet known from 1 to i and the shortest path has to be determined then pi(i) assumes a large enough value (such as maxint, for example). It seems to be clear that pi(1)=0 for the initial node of paths, and qsi(1) does not exists.
Now we shall describe a general labeling algorithm (because labels are used) to determine a shortest path between a given pair of nodes. In this general labeling algorithm we will use set X as a working variable and we will denote by d(i,j) the distance assigned to the arc (i,j).

The General Labeling Algorithm

With the general labeling algorithm we will get the following steps to solve the problem above:
From 1, the initial node, we will label nodes 2, 3 and 4, one at a time, with (7,1), (1,1) and (32,1), respectively. As a consequence, X={2,3,4}.
As X is not the empty set, let us choose some node in X; for example, node 2. As a consequence, X={3,4}. From node 2, we only assign the label (17,2) to node 5; in fact, arc (2,3) begins also in node 2, but pi(2) + d(2,3) > pi(3) and pi(3) is not changed. At this moment, X={3,4,5} and we have to choose another node in X, for example, node 3; as a consequence, X={4,5}.
From node 3 we will assign the label (13,3) once pi(3) + d(3,5) < pi(5). However, since node 3 belongs to X, this set is not changed. Now we can choose node 4 in X and the only consequence is to remove it from X; as 5 is the only node in X, it is now choosen and removed from this set. But from node 5 we will assign the label (19,5) to node 4 and X={4}.
Removing node 4 from X and as no label can be assigned from this node, we will finish the algorithm. The shortest path between nodes 1 and 5 is then determined using the second value of each label, begining in the terminal node. That is, node 5 was labeled from node 3 which was labeled from node 1; so, the shortest path is {1,(1,3),3,(3,5),5}.

Note however that the algorithm is not valid for all instances of the Optimal Path Problem. For instance, let us change the distance of arc (1,2) such that d(1,2)= -7. From the general labeling algorithm, it results clear that node 2 can always be labeled from node 1 and node 1 can always be labeled from node 2. That is, X has always at least one element which implies the nonfinitness of the algorithm. So we must take into account, at least, finitness of the algorithm.

Algorithm finitness is always related with the existence of a cycle - the absorvent cycle.

network Let us consider now, one other instance of the Optimal Path Problem depicted in the figure on the left.
Let us assume that the arc cost is the first value assigned to each arc and the second value is the arc time. Let us define the path cost (time) as the sum of its arcs cost (time) and let us determine a path with minimum cost - time ratio.
It is clear that from node 1 to node 4, there are only two paths; that is, path A = {1,(1,3),3,(3,4),4} and path
B = {1,(1,2),2,(2,3),3,(3,4),4}.
According this exaustive search, the cost - time ratio of path A is (1 + 1) / (9 + 1) = 2/10 and the cost - time ratio of path B is (0 + 0 + 1) / (1 + 1 + 1) = 1/3. That is, path A is the minimum cost - time ratio path.
According the general labeling algorithm, from node 1 the label (0/1,1) is assigned to node 2 and the label (1/9,1) to node 3. At this time X = {2, 3}; so, picking up node 2 in X we change the label of node 3 to (0/2,2) since the cost - time ratio of the sub - path {1,(1,2),2,(2,3),3} is less than the cost - time ratio of the sub - path {1,(1,3),3}. Now, X = {3} and from node 3 we assign the label ((0+0+1)/(1+1+1),3) to node 4. After a few more trivial steps the algorithm finishes with B = {1,(1,2),2,(2,3),3,(3,4),4} as the minimum cost - time ratio path, which is not correct. So, something fails with the algorithm. In fact, the General Labeling Algorithm is supported by the so called Principle of Optimality which asserts that the optimal path is formed by optimal sub-paths. This is not the case of the last solved problem...

So, when faced with an Optimal Path Problem we must be concerned with the non existence of absorvent cycles to assure finiteness of the general labeling algorithm and also with the existence of an optimal path from the initial node to all the others such as all its sub - paths from the initial node are also optimal.
Notice that assuming finitness of the problem and the existence of some optimal path verifying the Principle of Optimality, the general labeling algorithm determines the optimal path from agiven node s to all the others nodes, i.e., the optimal tree rooted at s.

According the optimality criteria, that is, the objective function, we may consider several types of Optimal Path Problems, some of them enumerated in the following table.

Maximum Capacity Path Problem

Fractional Path Problems

  • Minimum Cost-Time Ratio Path Problem
  • Minimum Cost-Capacity Ratio Path Problem
  • Minimum Cost-Reliability Ratio Path Problem
  • Quickest Path Problem

    Shortest Path Problems

  • Shortest Path Problem
  • K-th Shortest Path problem
  • Multiobjective Shortest Path Problem
  • Constrained Shortest Path Problem


  • See some "Shortest Path Web Pages"


    This introduction to the "Optimal Path Problems" is a constantly envolving document and feedback is appreciated.


    Contributer: Ernesto Martins

    Referenced by:

    Refers to:

    Status: First version.


    This introduction has received accesses since 9 May 1999.


    Return

    TOP

    ROOT of OPP PAGE

    WORMS Virtual Encyclopedia