DAG Kth shortest path dynamic programming

Question

This is not for homework. I am working through a practice test (not graded) in preparation for a final in a couple of weeks. I have no idea where to go with this one.

Let G = (V;E) be a DAG (directed-acyclic-graph) of n vertices and m edges.

Each edge (u; v) of E has a weight w(u; v) that is an arbitrary value (positive, zero, or negative).

Let k be an input positive integer.

A path in G is called a k-link path if the path has no more than k edges. Let s and t be two vertices of G. A k-link shortest path from s to t is defined as a k-link path from s to t that has the minimum total sum of edge weights among all possible k-link s-to-t paths in G.

Design an O(k(m+ n)) time algorithm to compute a k-link shortest path from s to t.

Any help on the algorithm would be greatly appreciated.

So what shortest path algorithms do you know that handle DAGs with arbitrary weights? I'm pretty sure 99% of CS undergrad curriculums teach precisely one. Could that algorithm help you here? — rliu
Well it was mentioned but nothing anywhere near the runtime that this question requires... — Bored Foo
Because the algorithms that have been mentioned have very different run times. I am not sure if k=n would work because then the question would just ask for O(n(m+n)) — Bored Foo
What's the algorithm you're thinking of? And my point is that, if we're thinking of the same algorithm, then it has the correct runtime. It has a time complexity of O(n + k(m + n) + k) which is indeed O(k(m + n)). My hint was that you only think it's too slow because you think k is some small number... what if you set it to n? Then do you see how O(k(m + n)) can be slow? — rliu

yasen yasen · Accepted Answer · 2013-12-01T23:01:42

Let dp[amount][currentVertex] give us the length of the shortest path in G which starts from s, ends at currentVertex and consists of amount edges.

make all values of dp unset
dp[0][s] = 0

for pathLength in (0, 1, .. k-1)             // (1)
    for vertex in V
        if dp[pathLength][vertex] is set     
            for each u where (vertex, u) is in E    // (2), other vertex of the edge
                if dp[pathLength+1][u] is unset or greater than dp[pathLength][vertex] + cost(vertex, u)
                    set dp[pathLength+1][u] = dp[pathLength][vertex] + cost(vertex, u)

best = dp[k][t]
for pathLength in (0, 1, .. k)
    if dp[pathLength][t] < best
        best = dp[pathLength][t]

The algorithm above will give you the length of the k-link shortest path from s to t in G. Its time complexity is dominated by the complexity for the loop (1). The loop (1) alone has complecity O(k), while its inner part - (2) simply traverses the graph. If you use an adjacency list, (2) can be implemented in O(n+m). Therefore the overall complexity is O(k*(n+m)).

However, this will give you only the length of the path, and not the path itself. You can modify this algorithm by storing the previous vertex for each value of dp[][]. Thus, whenever you set the value of dp[pathLength+1][u] with the value of dp[pathLength][vertex] + cost(vertex, u) for some variables vertex, u, pathLength you would know that the previous used vertex was vertex. Therefore, you would store it like prev[pathLength+1][u] = vertex.

After that, you can get the path you want like. The idea is to go backwards by using the links you had created in prev:

pLen = pathLength such that dp[pathLength][t] is minimal
curVertex = t

path = []           // empty array
while pLen >= 0
    insert curVertex in the beginning of path
    curVertex = prev[pLen][curVertex]
    pLen = pLen - 1

path is stored the k-link shortest path from s to t in G.

DAG Kth shortest path dynamic programming

1 Answers