Shortest path with one skippable edge

Question

I have this problem: "Shortest path with one skippable edge. Given an edge-weighted digraph, design an E*log(V) algorithm to find a shortest path from s to t where you can change the weight of any one edge to zero. Assume the edge weights are nonnegative."

I don't understand what they want me to do. What does it mean to change the weight to zero? I think that I can change any edge in any shortest path to zero and it will still be the shortest.

Answer 1

First use Dijkstra to find the length S(v) of shortest path from s to v for every vertex v. Then use Dijkstra to find the length T(v) of shortest path from v to t for every vertex v. Then for every edge (v, w) find the sum S(v) + T(w) by using the rules above. Finally, choose the minimum path.

Note: In this approach we nullify the edge (v,w) weight and find the shortest path through (v,w)

Answer 2

The problem is simple.

Suppose that you have a shortest path with one skippable edge, p = v1,...,vi,vi+1,...,vm and (vi,vi+1) is a skipped edge
Obviously, a path(v1,...,vi) is a shortest path between v1 and vi
and a path(vi+1,...,vm) is a shortest path between vi+1 and vm
Define d(x,y) as the length of the shortest path between node x and node y
you can simply find d(s,x) and d(x,t) for all node x by dijkstra algorithm and now we have to choose the skipped edge one by one. In other words, the length of the shortest path with one skippable edge is

min( d(s,u) + d(v,t) ) for all edge (u,v) in the graph

and the time complexity is O(E log V) because of Dijkstra Algorithm