algorithm - Finding top 3 longest path in directed acyclic weighted graph -


i able use this algorithm find longest path in weighted dag (using topological sort , relaxing each edge). question if there algorithm find top 3 longest paths of dag? or, there javascript or java library implements algorithm?

you can compute first longest path, , can use following algorithm finding next longest path:

delete each edge of main longest path 1 one , run algorithm again find longest path on modified graph put deleted edge , delete 1 other edge.

why works?
need path not first longest path, second longest path must different in @ least 1 edge, if ignore 1 edge , find longest path each of edges find longest path don't share @ least 1 edge main longest path.
third longest path path longest path , doesn't share @ least 1 edge first , second longest path.


Comments