A layered graph is a connected graph whose vertices are partitioned in
to sets L-0 = {s}, L-1; L-2,..., and whose edges, which have nonnegati
ve integral weights, run between consecutive layers. Its width is max{
\L-i\}. In the on-line layered graph traversal problem, a searcher sta
rts at s in a layered graph of unknown width and tries to reach a targ
et vertex t; however, the vertices in layer i and the edges between la
yers i - 1 and i are only revealed when the searcher reaches layer i -
1. We give upper and lower bounds on the competitive ratio of layered
graph traversal algorithms. We give a deterministic on-line algorithm
which is O(9(w))-competitive on width-w graphs and prove that for no
w can a deterministic on-line algorithm have a competitive ratio bette
r than 2(w-2) on width-w graphs. We prove that for all w, w/2 is a low
er bound on the competitive ratio of any randomized on-line layered gr
aph traversal algorithm. For traversing layered graphs consisting of w
disjoint paths tied together at a common source, we give a randomized
on-line algorithm with a competitive ratio of O(log w) and prove that
this is optimal up to a constant factor.