Shortest Constrained Path

Applet kann nicht gestartet werden

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.