Version: 1.0
Last Update: December, 1995
Subject Index:
One Liner: Optimal path problems
Body:
The paper The Optimal Path problem is on line for now.
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).
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.
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 subpaths. 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 ProblemFractional Path Problems 
Quickest Path ProblemShortest Path Problems

Contributer: Ernesto Martins
Referenced by:
Refers to:
Status: First version.
Return