Longest path between from a source to certain nodes in a DAG

views:

1431

answers:

+3 Q:

Longest path between from a source to certain nodes in a DAG

+3 A:

Wikipedia to the rescue! Their page on this problem indicates that in the general case, your problem is NP-Complete. However, since you have a directed acyclic graph, you can invert all the edge weights and run the Bellman-Ford algorithm to solve it. The B-F algorithm normally computes single-source shortest paths in a graph. With inverted edge weights, it should produce the longest paths.

Kristo 2009-02-28 15:55:14

Thanks Kristo. But as the graph is DAG therefore wont B-F will be costly? The graph is quite sparsely populated so V*E could become expensive. I am already trying Dijkstra's which serves the purpose of given longest paths but looking for a way to filter out extra edges.

funkyprogrammer 2009-02-28 16:24:15

@Kristo: The algorithm you gave in your update won't produce the maximum-weight path on a general DAG, as it favours paths containing few edges. But if all paths have the same number of edges it will work fine.

j_random_hacker 2009-03-03 13:06:38

Can you explain why? Dijkstra's Algorithm seeks to minimize the cost of the path, not the number of edges. It cannot handle cycles, but the OP already said his graph was acyclic.

Kristo 2009-03-03 14:13:59

If you add abs(most-negative edge weight) (say z) to each edge, you effectively add k*z to each path with k edges. Dijktra will find the minimum over all paths P of the expression (-sum(edges in P) + |P| * z), which is different than minimising (-sum(edges in P)) if |P| can vary.

j_random_hacker 2009-03-04 04:00:38

Ok I understand. I've reverted my changes. I suppose if my suggestion would have worked, then Wikipedia would have suggested it instead of Bellman-Ford. :-)

Kristo 2009-03-04 15:21:27

It's a tricky one... One of those approaches that feels like it *should* work! :)

j_random_hacker 2009-03-05 00:13:16

ansaurus

tags:

views:

answers:

Longest path between from a source to certain nodes in a DAG

related questions