4

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.

alt text

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

Glorfindel
  • 21,988
  • 13
  • 81
  • 109

2 Answers2

4

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.

Michael Kristofik
  • 34,290
  • 15
  • 75
  • 125
  • 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. –  Feb 28 '09 at 16:24
  • 1
    @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 Mar 03 '09 at 13:06
  • 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. – Michael Kristofik Mar 03 '09 at 14:13
  • 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 Mar 04 '09 at 04:00
  • 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. :-) – Michael Kristofik Mar 04 '09 at 15:21
  • It's a tricky one... One of those approaches that feels like it *should* work! :) – j_random_hacker Mar 05 '09 at 00:13
0

I believe the following will give you the largest number of steps to reach the destination (not the actual path, just the number of steps). This doesn't take edge weights into account. This works by coalescing nodes starting from src until no neighbors are left except the destination node.

longestPath (src, dest) =
    if (neighbors(src) == [dest]) then 1
    else 1 + longestPath(newNode(concat (map neighbors (neighbors src))), dest)
gcbenison
  • 11,723
  • 4
  • 44
  • 82