Shortest Constrained Path
This Applet demonstrates the calculation of a shortest path in a weighted,
directed, anti-cyclic graph whose edge weights are not set to a fixed
value but an (integer) interval. The precise length of this interval may
be quested for extra costs.
For simplicity not all possible paths are displayed, only paths from a set source (startvertex) S to a sink (targetvertex) T.
We are now looking for paths containing quested edges whose costs are guaranteed to lie in an interval of width at most k.
The algorithm used was developed by T. Feder, R. Motwani, L. O'Callaghan, C. Olson and R. Panigrahy in "Computing Shortest Paths with Uncertainty", Stanford University.