Suurballe's algorithm

Definitions

• G represent a graph
• P represent a path
• s represent source start vertex
• w(u, v) mean edge weight from vertex u to v
• d(u, v) mean short path cost from vertex u to v

Algorithm

1. Find shortest path P1
2. Recalculate the edge weith by w′(u,v) = w(u,v) − d(s,v) + d(s,u)
3. Create a residual graph Gt formed from G by removing the edges of G on path P1 (leave a reserve zero path)
4. Find the shortest path P2 in the residual graph Gt
5. Discard the reversed edges of P2 from both paths

The remaining edges of P1 and P2 form a subgraph have no common edges.
Return the two disjoint paths from the subgraph.

Example

• Figure A illustrates a weighted graph G.
• Figure B calculates the shortest path P1 from A to F (A–B–D–F).
• Figure C illustrates the shortest path tree T rooted at A, and the computed distances from A to every vertex (u).
• Figure D shows the residual graph Gt with the updated cost of each edge and the edges of path ‘P1 reversed.
• Figure E calculates path P2 in the residual graph Gt (A–C–D–B–E–F).
• Figure F illustrates both path P1 and path P2.
• Figure G finds the shortest pair of disjoint paths
  Combining the edges of paths P1 and P2 and then discarding the common reversed edges between both paths (B–D).
  As a result, we get the two shortest pair of disjoint paths (A–B–E–F) and (A–C–D–F).

https://en.wikipedia.org/wiki/Suurballe%27s_algorithm