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.
