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
Post a Comment