jisan047's blog

By jisan047, history, 5 years ago,

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?

• +1

 » 5 years ago, # |   +8 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.
 » 5 years ago, # |   0 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 :)
•  » » 5 years ago, # ^ |   0 Isn't it costly in the respect of time?
•  » » » 5 years ago, # ^ |   0 It depend on the graph and the length of the initial Shortest Path
 » 18 months ago, # |   0 jisan047 You can find kth shortest path between two node s and t. https://en.wikipedia.org/wiki/K_shortest_path_routing