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.

Over all edges $($u$,$ v$)$ in G$,$ find the minimum dist$\_$to$($G$,$ s$,$ u$)+$ dist$\_$to $($GR$,$ t$,$ v$)58$

s w t

vu $2$

$17$

$56$

$899$

source destination

weight

s w t

vu $2$

$17$

$56$

$899$

source destination

weight

G

GR