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

Hi Experts, How do i find the longest path from single source to all final destinations i.e. For source i1, Give longest path between i1 -> o1 and i1 -> o2.

The legends described in the above graph are as follows: (i1, i2) are start nodes (o1, o2) are end nodes (1-8) are sub graphs The edges may have +ive/-ive weights

The longest paths in this network are in the following order:

Worst path: i1 -> 1 -> 4 -> o1

Then, all paths i1 … -> … o1

Then i1 -> 5 -> 6 -> o2

Need a way to ignore selection of (i1 -> 3) or (3 -> 4) subnetworks even though they are longer than i1 -> 5

From stackoverflow

• 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.

  funkyprogrammer : 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.

  j_random_hacker : @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.

  Kristo : 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.

  j_random_hacker : 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.

  Kristo : 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. :-)

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