Pair of non-intersecting shortest paths on undirected graph

Specific Domains Graphs
,
2

No guarantees that it is correct, but I would at least try the following:

  1. Find the shortest path from i to j.
  2. Remove all edges from the non-endpoint nodes on that path.
  3. Find a new shortest path from i to j.
3 Likes