It is, of course, quite easy to find the best completely-disjoint route. In particular, you can simply find the best route, remove all of the links in the best route from the network (or set their costs to be arbitrarily high), and then re-calculate the "best" route. The problem with this approach is that when all of the links in the best route are removed it may disconnect the origin from the destination (i.e., there may no longer be a path from the origin to the destination). In addition, even when the network does not become disconnected, the completely-disjoint path may be too dissimilar to be useful.

One is then naturally led to consider iteratively removing the links in the original best path. However, this can be quite expensive computationally because you actually must remove all combinations of links (e.g., 1 only, 1 and 2, 1 and 3, 1 and 4, ..., 2 only, 2 and 3, ...).

Instead, the following demonstration uses a method known as Lagrangian Relaxation to solve the problem.

Instructions:

1. Select your starting point by choosing Set Orig. and then clicking on the map. (It will be drawn in green.)
2. Select your ending point by choosing Set Dest. and then clicking on the map. (It will be drawn in red.)
3. Find the best path from your origin to your destination by clicking on Best Path .
4. Find an alternative path by clicking on Alt. Path . This alternative path will include only a few links in the best path.

Some interesting examples:

• Arecibo to Ponce (no links in common);
• Ponce to Salinas (one link in common, at the end); and
• Bayamon to Florida (one link in common, in the middle).