Massachusetts Institute of Technology Professors Ronald L. Rivest and Sivan Toledo

Question

Suppose you want to get from s to t on weighted graph G with nonnegative edge weights, but you would like to stop by u if it isn’t too inconvenient. (Here too inconvenient means that it increases the length of your travel by more than 10%.) Describe an efficient algorithm that would determine an optimal s to t path given your preference for stopping at u along the way if not too inconvenient. It should either return the shortest path from s to t, or the shortest path from s to t containing u.

Comments

Run Dijkstra’s algorithm twice, once from s and once from u. The shortest path from s to t containing u is composed of the shortest path from s to u and the shortest path from u to t. Compare the length of this path with the length of the path from s to t, and choose the one to return based on their lengths.

Answer given by MIT