jisan047's blog

Need help .
By jisan047, history, 8 years ago, In English

How to find second shortest path? I can find shortest path between 2 nodes. But i need to find second shortest path between 2 nodes. How to do this?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Consider there isn't edge with negative cost.

The second path differs from first one in at least one edge, it has at least one edge that doesn't appear in first one. For each vertex find it's distance from Source (dsv) and Destination (ddv).

Find some shortest path, for each edge that doesn't appears in this shortest path, consider this edge connects v and u and it's cost is w, the shortest path from Source to Destination that passes from this edge is min {dsv + w + ddu, dsu + w + ddv}.

Finally find minimum of these values, it's the answer.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My Idea is that you can save the Edges used in the shortest path in a vector, disable an Edge every time and try to find the shortest path , the shortest path found while ignoring one of the Edges used in the shortest path is the Second shortest path :)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't it costly in the respect of time?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It depend on the graph and the length of the initial Shortest Path

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

jisan047 You can find kth shortest path between two node s and t. https://en.wikipedia.org/wiki/K_shortest_path_routing

→ Reply