maximum weighted path(s) in a DAG

Question

Given a weighted directed acyclic graph (DAG), I need to find all maximum weighted paths between the start node(s), i.e. zero incoming edges, and the end node(s), i.e. zero outgoing edges. My current approach is doing the followings.

Add an extra node $S$ (source) and put directed edges to all starting nodes with zero weight. Similarly, add a sink node $T$ and put directed edges from all end nodes to $T$ with zero weight. Now, the problem is to find all maximum weighted paths between $S$ and $T$. Make the edge weights negative, i.e. weight $w$ becomes $-w$. Find the all single-source shortest path from $S$.

My question is, if there is any other efficient method to achieve this. The other thing is that, I need to find all maximum weighted paths if there exists more than one such paths. How can I find all maximum weighted paths efficiently?

Does maximum flow algorithm help?

Answer 1

Your strategy is close, but probably needs some clarification. This is essentially equivalent to finding the longest path in DAGs, which can be done easily in a few ways easiest of which, similar to what you describe:

• Negating edge weights and running a DAG-Shortest-Path algorithm.

In your case we could implement it similar to the following (transcribed mostly from CLRS 24.2) assuming input is an adjacency list:

0.  Max-Weight-Paths(Graph G(E, V)):
1.    add Super-Source S, and Super-Sink T // takes O(V + E)
2.    negate all edge weights              // takes O(V + E)
3.    topological sort G.V                 // takes O(V + E)
4.    for each vertex u in sorted order:
5.      for each vertex v in G.adj[u]:
6.        Relax(u, v)                      // 4-6 takes O(V + E)

Now for returning all max weight paths we can simply modify the relaxation step (6) a little bit. Instead of only containing a back pointer to one parent, we can maintain a linked list of back pointers to all parents of equal total distance like so:

0.  Relax(Vertex u, Vertex v):
1.    if distance(v) > distance(u) + w(u, v):
2.      distance(v) = distance(u) + w(u, v)
3.      parents(v) = {u}
4.    elif distance(v) == distance(u) + w(u, v):
5.      add u to parents(v)

Assuming parents(v) is maintained as a list, the Relax step still takes $O(1)$.

Then in the end you can return all max weight paths by starting at the sink T and traversing back up through parents(T) an so on. This traversal will return a DAG itself if multiple max weight paths exist. So just be smart about the traversal and the whole thing should take $O(V + E)$.

---

Edit, when I say be smart about the returning traversal, keep in mind a bad case scenario, something like this where all edge weights are equal:

There would technically be $6^2$ max weight paths, you could expand this example to get graphs with very large amounts of max weight paths due to combinatorics. So it might be more useful to return the DAG of max-weight paths rather than each individual. Although if you must return individual paths then you might be out of luck, because there are a lot of possibilities.

Answer 2

You should try to understand what topological sort does. It finds an order v1,v2,...vn of DAG such that there is never an edge (vx, vy) where x > y.

Once you have top sort graph, then you can start in topological order of vertices, and then for each outgoing edge, start to RELAX the destination vertex.

Note that the RELAX function could either be max cost or min cost. The algo works in both the cases. To understand why it works, you'll need to understand why the algo works for Shortest Path solution first. You can check any algorithm book (Goodrich Tamassia / Cormen etc) to understand the proof