QUESTIONS FROM OLD EXAMINATIONS
About Optimal Path Problems

Let _{ }
be a given network, where is the set of
nodes and the set of arcs.
Let s be a given node of
and let c_{ij} be a given real number associated with each arc
(i,j). For any cycle C in
_{ }
the C cost c(C) is the sum of the
c_{ij} real values associated with the arcs of C.
Assume the non existence of cycles with negative cost and
describe an algorithm to determine a cycle which minimize c(C)
over C^{*}, the set of cycles in
_{ }
such that s is one of its nodes.

Describe the shortest path problem and the maximal capacity path problem.

Let _{ }
be a given network, and let s and t
be two distinct nodes of _{ }.
Let us assume the existence
of at least one path from s to i and from i to t,
for any node i different from s and t.
Prove that the shortest path (from s to t) problem satisfy the
Principle of Optimality
if and only if there are no negative cycles in
_{ }.

Describe the minimal costtime ratio path problem and show, with an
example, that it can not be solved by labeling algorithms.

Describe an algorithm to determine the maximal capacity path in the set of
the shortest paths.

Describe an algorithm to determine the shortest path in the set of
the maximal capacity paths.

Describe an algorithm to determine the shortest path between a given pair of
nodes of a given network, with the minimal number of arcs.
Note: The efficiency of the algorithm will be considered in the
classification.

Describe an algorithm to determine a path between a given pair of nodes of
a given network with minimal number of arcs.
Note: The efficiency of the algorithm will be considered in the
classification.

Let _{ }
be an acyclic network such that
={1,...,n}
and (i,j) is an arc if and only if i<j.

Describe an _{ }
algorithm to determine the shortest
tree rooted at node 1, i.e., the tree of the shortest paths from node 1
to each node {2,...,n}.

Describe an _{ }
algorithm to determine the shortest
tree rooted at node n, i.e., the tree of the shortest paths from each node
{1,...,n1} to node n.

Let _{ }
denote the shortest distance from a given node
s to a node i.
Prove that
_{ }
holds for any arc (i,j), where
_{ }
denotes the distance assigned to arc (i,j).

Describe the adressed calculation sort form of the label seting algorithm
for the maximal capacity path problem.
About Maximal Flow  Minimal Cut Problem

Let
_{ }
be given network and s and t two given different nodes of
_{ }
and let
_{ }
be a minimal cut for s and t.
Prove that
_{ }
is a minimal cut for
_{}
and
_{}
for all
_{
}
and
_{
}

Let
_{ }
be given network and s and t two given different nodes of
_{ }
and let
_{ }
be a minimal cut for s and t.
Denoting by
_{ }
and
_{ }
the amount of flow in arc (i,j) and the capacity
of arc (i,j) respectively,
prove that
_{ }
=
_{ } holds for any arc
(i,j) of
_{.}

Let
_{ }
be given network and s and t two given different nodes of
_{ }
and let
_{ }
be a minimal cut for s and t.
Denoting by
_{ }
the amount of flow in arc (i,j),
prove that
_{ }
holds for any arc
(i,j) of
_{.}
PAGE OF CONTENTS
Optimal Path Problem Web Page
BACK MATH'S DEPARTMENT