15-1 Longest simple path in a directed acyclic graph

Suppose that we are given a directed acyclic graph $G = (V, E)$ with real-valued edge weights and two distinguished vertices $s$ and $t$ . Describe a dynamic-programming approach for finding a longest weighted simple path from $s$ to $t$ . What does the subproblem graph look like? What is the efficiency of your algorithm?

We will make use of the optimal substructure property of longest paths in acyclic graphs. Let $u$ be some vertex of the graph. If $u = t$, then the longest path from $u$ to $t$ has zero weight. If $u \ne t$, let $p$ be a longest path from $u$ to $t$. Path $p$ has at least two vertices. Let $v$ be the second vertex on the path. Let $p'$ be the subpath of $p$ from $v$ to $t$ ($p'$ might be a zero-length path). That is, the path $p$ looks like

$$u \to v \overset{p'}{\leadsto} t.$$

We claim that $p'$ is a longest path from $v$ to $t$.

To prove the claim, we use a cut-and-paste argument. If $p'$ were not a longest path, then there exists a longer path $p''$ from $v$ to $t$. We could cut out $p'$ and paste in $p''$ to produce a path $u \to v \overset{p''}{\leadsto} t$ which is longer than $p$, thus contradicting the assumption that $p$ is a longest path from $u$ to $t$.

It is important to note that the graph is acyclic. Because the graph is acyclic, path $p''$ cannot include the vertex u, for otherwise there would be a cycle of the form $u \to v \leadsto u$ in the graph. Thus, we can indeed use $p''$ to construct a longer path. The acyclicity requirement ensures that by pasting in path $p''$ , the overall path is still a simple path (there is no cycle in the path). This difference between the cyclic and the acyclic case allows us to use dynamic programming to solve the acyclic case.

Let $dist[u]$ denote the weight of a longest path from $u$ to $t$. The optimal substructure property allows us to write a recurrence for $dist[u]$ as

$$ dist[u] = \begin{cases} 0 & \text{if $u = t$}, \\ \max\limits_{(u, v)\in E}{w(u, v) + dist[v]} & \text{otherwise}. \end{cases} $$

This recurrence allows us to construct the following procedure:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
LONGEST-PATH-AUS(G, u, t, dist, next)
    if u == t
        dist[u] = 0
        return (dist, next)
    else if next[u] ≥ 0
        return (dist, next)
    else next[u] = 0
        for each vertex v ∈ G.Adj[u]
            (dist, next) = LONGEST-PATH-AUX(G, v, t, dist, next)
            if w(u, v) + dist[v] > dist[u]
                dist[u] = w(u, v) + dist[v]
                next[u] = v
    return (dist, next)

(See Section 22.1 for an explanation of the notation $G.Adj[u]$.)

$\text{LONGEST-PATH-AUX}$ is a memoized, recursive procedure, which returns the tuple $(dist, next)$. The array $dist$ is the memoized array that holds the solution to subproblems. That is, after the procedure returns, $dist[u]$ will hold the weight of a longest path from $u$ to $t$. The array $next$ serves two purposes:

  • It holds information necessary for printing out an actual path. Specifically, if $u$ is a vertex on the longest path that the procedure found, then $next[u]$ is the next vertex on the path.
  • The value in $next[u]$ is used to check whether the current subproblem has been solved earlier. A value of at least zero indicates that this subproblem has been solved earlier.

The first if condition checks for the base case $u = t$. The second if condition checks whether the current subproblem has already been solved. The for loop iterates over each adjacent edge($u, v)$ and updates the longest distance in $dist[u]$.

What is the running time of $\text{LONGEST-PATH-AUX}$? Each subproblem represented by a vertex $u$ is solved at most once due to the memoization. For each vertex, we examine its adjacent edges. Thus, each edge is examined at most once, and the overall running time is $O(E)$. (Section 22.1 discusses how we achieve $O(E)$ time by representing the graph with adjacency lists.)

The $\text{PRINT-PATH}$ procedure prints out the path using information stored in the next array:

1
2
3
4
5
6
PRINT-PATH(s, t, next)
    u = s
    print u
    while u != t
        print "→" next[u]
        u = next[u]

The $\text{LONGEST-PATH-MAIN}$ procedure is the main driver. It creates and initializes the $dist$ and the $next$ arrays. It then calls $\text{LONGEST-PATH-AUX}$ to find a path and $\text{PRINT-PATH}$ to print out the actual path.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
LONGEST-PATH-MAIN(G, s, t)
    n = |G.V|
    let dist[1..n] and next[1..n] be new arrays
    for i = 1 to n
        dist[i] = -∞
        next[i] = -1
    (dist, next) = LONGEST-PATH-AUX(G, s, t, dist, next)
    if dist[s] == -∞
        print "No path exists"
    else print "The weight of the longest path is" dist[s]
        PRINT-PATH(s, t, next)

Initializating the dist and next arrays takes $O(V)$ time. Thus the overall running time of $\text{LONGEST-PATH-MAIN}$ is $O(V + E)$.

Alternative solution

We can also solve the problem using a bottom-up aproach. To do so, we need to ensure that we solve "smaller" subproblems before we solve "larger" ones. In our case, we can use a topological sort (see Section 22.4) to obtain a bottom-up procedure, imposing the required ordering on the vertices in $\Theta(V + E)$ time.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
LONGEST-PATH2(G, s, t)
    let dist[1..n] and next[1..n] be new arrays
    topologically sort the vertices of G
    for i = 1 to |G.V|
        dist[i] = -∞
    dist[s] = 0
    for each u in topological order, starting from s
        for each edge (u, v) ∈ G.Adj[u]
            if dist[u] + w(u, v) > dist[v]
                dist[v] = dist[u] + w(u, v)
                next[u] = v
    print "The longest distance is" dist[t]
    PRINT-PATH(s, t, next)

The running time of $\text{LONGEST-PATH2}$ is $\Theta(V + E)$.