Let G be a weighted directed graph with the following properties. 1. G = G0 + G1 + G2 + ... + Gn 2. G0 consists of one vertex, s, while Gn consists of one vertex, t. For any 0 < i < n, Gi consists of two vertices. 3. For any 0 <= i < n, there is a weighted directed edge from each vertex of Gi to each vertex of G{i+1}, and there are no other edges. 4. All weights are either 1 or 2. The problem is to find the smallest weight path from s to t that you can. Offline Problem. You are given the entire graph G in advance. There are easy and well-known algorithms which can find the minimum weight path in the offline case. Online Problem. Let Ei be the set of edges from G{i-1} to Gi. Your path path must start at s, and at the i^{th} step, you must augment your path by choosing a vertex in Gi. If i < j, You cannot see the weights of Ej before you choose a vertex in Gi. You are, at first, given only the weights of E1. At step 1, you pick a vertex in G1, after which, you can see the weights of E2. You then pick a vertex in G2, after which you can see the weights of E3, and so forth. An online algorithm for this problem is defined to be any algorithm which chooses a path according to the above rules. There is no online algorithm for this problem which is guaranteed to pick the optimal path. What is the best that an online algorithm can achieve?