Shortest path with one skippable edge

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)

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

The previous answers seem to suppose that Dijkstra gives the shortest distance from every vertex to every vertex, but this is not the case.

If you execute Dijkstra only once, starting from s, you have the shortest path from s to every vertex.

To find the shortest distance from every vertex to t, it is necessary to execute Dijkstra again starting from t after reversing every edge of the graph.

The complete solution is:

1) Execute Dijkstra on the graph G starting from s to obtain the shortest distance T(v) between s and any v.

2) Reverse all the edges to obtain the reversed graph G'

3) Execute Dijkstra on the graph G' starting from t to obtain the shortest distance R(v) between t and any v.

4) The one to skip is the edge e(v1 --> v2) for which T(v1) + R(v2) is minimum.

5) The path to follow is a concatenation of the shortest path between s and v1 given by the first Dijkstra and the shortest path between v2 and t given by the second Dijkstra.