Finding Minimal Paths in Layered Graphs
A Challenge Problem in Algorithms and Data Structures
Revised November 17, 2005.
The purpose of these problems is to provide a challenge to the top students,
meaning those who master the regular material of the course and would like
to learn more.
Do not try to work these problem to improve a poor grade ... if you are doing
badly in the course, concentrate on the regular material.
Layered Graphs
A
layered graph is defined to be
a connected graph whose vertices are partitioned into sets
L0={s},
L1, L2, ...
called layers,
and whose edges, which have non-negative integral weights, run between
consecutive layers. That is, if a node
x
is in
Li,
then all neighbors of
x
are either in
Li-1 or Li+1.
We say that a layered graph
G has width
w if there are no more than
w nodes in any layer.
We assume that L0 consists of
a single node s,
which we call the
source.
Minimal Paths
One problem is to construct a minimal path from
s to a target node t.
(Unlike the problem given by
Fiat et al., we allow the path to "snake" back and forth
within the layers.
Here is an example of a layered graph of width 3.)
This problem can be solved using standard methods,
such as Dijkstra's algorithm.
The Online Condition
We now impose a condition to make the problem harder.
The graph is given to us online, which means that
the algorithm can see only one layer at a time, and each layer
only once. Furthermore, the algorithm has limited memory available.
Here are the specific restrictions:
-
The memory available to the algorithm is O(w2),
where w is the width of
G. Yet, the total size of
G could be much larger.
-
The algorithm can only read two adjacent layers at a time.
If it decides to read Li,
it can never again read Li-2.
While it is reading
Li-1 and Li,
it also reads the edges between them. These edges will not be visible
after the algorithm decides to read Li+1.
-
t is in Ln
for some
n, but the algorithm does not know the value of
n until it reads
Ln.
-
The output of the algorithm is simply the weight of the minimal path.
Because of the memory restriction, we cannot expect the algorithm
to output the path, since it could be longer than the available memory.
I believe there exists such an algorithm that finds the minimal weight of
any path from s to t in
O(nw3) time. Find it. Can you do better?
