Shortest path with one skippable edge
graph, shortest-path
Solution
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)`
Problem
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.