In Directed Acyclic graph, find the weight of a path is the sum of the weights of the directed edges comprising the path

Question

You are given a directed acyclic graph G = (V,E). Each directed edge e ∈ E has weight w_e associated with it. Given two vertices s,t ∈ V such that s has no incoming edge and t has no outgoing edge, we are interested in a maximum weight directed path that begins at s and ends at t. The weight of a path is the sum of the weights of the directed edges comprising the path. (A directed graph is acyclic if it has no directed cycles in it.)

How do I solve it by using dynamic programming techniques? I have been stuck for a while, any tips is appreciated:D

@n.m. I did notice we can use Dijstra to solve it but how do we write a recurrence relation if I have to solve the problem by using dynamic programming? — jy l

Alchemy Alchemy · Accepted Answer · 2018-11-18T05:20:57

The key here is an understanding that "dynamic programming" just means that for some function f(x), any repeated executions of f for some distinct input x results in either a different result or execution path. From this definition we can consider caching to be an instance of dynamic programming.

So let's start with an implementation without dynamic programming. Using backtracking, we can perform a DEPTH FIRST (this will be important later) set of traversals starting from s and ending at t.

let P(a,b) be a path from a->b
let w(p) be the total weight of some path p
let K be the exhaustive set of P(s,t) // a.k.a every path that exists

// Returns Max(p) p  ∈ K
function findMaxPath(G)
    return findMaxPath(s)

// Returns Max(P(n, t))
function findMaxPath(n)
   if (n === t)
      return an empty path // we are already at the target
   declare p = null
   for each e of n // every outgoing edge
     let q = G(n, e)
     let l = findMaxPath(q) // get the maximum path from the neighbor indice to t
     if (l == null) continue
     l = e + l // prepend the outgoing end to the max path of the child node
     if (w(l) > w(p)) p = l // this is most expensive outgoing end that eventually reaches t
   return p // return null if we can't reach t

The problem with this solution is that it is really slow. In particular, you end up recalculating a LOT of paths. Take the following graph:

In the process of calculating the path from P(s, t), you end up executing findMaxPath(n) the following times for each n

findMaxPath(s) 1
findMaxPath(a) 1
findMaxPath(b) 1
findMaxPath(c) 1
findMaxPath(d) 3
findMaxPath(e) 3
findMaxPath(f) 3
findMaxPath(g) 3
findMaxPath(h) 9 (wow!)

In this example findMaxPath(h) has to get calculated 9 times, a number that can increase dramatically in more complex topologies (this one is fairly trivial). So to increase execution time, we can keep track of a "cache" of calls to findMaxPath(n). This is "dynamic" because the execution path of a function changes over time with identical variable inputs.

let P(a,b) be a path from a->b
let w(p) be the total weight of some path p
let K(n) be the exhaustive set of P(n,t) // a.k.a every path that exists
let C be a cache of Max(w(p)) p ∈ K(n)
// Returns Max(w(p)) p ∈ K(s)
function findMaxPath(G)
    return findMaxPath(s)

// Returns Max(P(n, t))
function findMaxPath(n)
   if exists C[n]
     return C[n] // we already know the most expensive path from n->t
   if (n === t)
      return an empty path // we are already at the target
   declare p = null
   for each e of n // every outgoing edge
     let q = G(n, e)
     let l = findMaxPath(q) // get the maximum path from the neighbor indice to t
     if (l == null) continue
     l = e + l // prepend the outgoing end to the max path of the child node
     if (w(l) > w(p)) p = l // this is most expensive outgoing end that eventually reaches t
   C[n] = p
   return p // return null if we can't reach t

This gives us a total cache "hit" of 16/25 making the runtime substantially faster

In Directed Acyclic graph, find the weight of a path is the sum of the weights of the directed edges comprising the path

1 Answers