Graph Reduction

75 Views Asked by At

Let G = (V,E) and s,t $\in$ V the input.

Let "at-least-two shortest path" be the shortest path between two vertices($s$,$t$) that goes through two edges at least.

How can I reduce this problem to the "single source shortest path" problem (which return the shortest path between two vertices($s$,$t$)) with runtime of O( $\lvert V\rvert$ + $\lvert E\rvert$)? .

1

There are 1 best solutions below

0
On BEST ANSWER

If $s$ and $t$ are adjacent and $d(s) = 1$ or $d(t) = 1$ then there is no solution.

If $s$ and $t$ are adjacent and $d(s), d(t) \ge 2$ then remove the edge $st$. Now apply the shortest path algorithm of your choice.

If $s$ and $t$ are not adjacent then the shortest path between them, if it exists, must have at least two edges.