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:
  1. 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.
  2. 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.
  3. t is in Ln for some n, but the algorithm does not know the value of n until it reads Ln.
  4. 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?