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?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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?
Name |
---|
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.
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 :)
Isn't it costly in the respect of time?
It depend on the graph and the length of the initial Shortest Path
jisan047 You can find kth shortest path between two node s and t. https://en.wikipedia.org/wiki/K_shortest_path_routing