algorithm - DAG 第 K 最短路径动态规划

Question

这不是作业。我正在通过练习测试(未评分)为几周后的期末考试做准备。我不知道该去哪里。

设 G = (V;E) 为 n 个顶点和 m 条边的 DAG(有向无环图)。

E 的每条边 (u; v) 都有一个权重 w(u; v)，它是一个任意值(正、零或负)。

设 k 为输入正整数。

如果路径不超过 k 条边，则 G 中的路径称为 k-link 路径。令 s 和 t 为 G 的两个顶点。从 s 到 t 的 k-link 最短路径定义为从 s 到 t 的 k-link 路径，它在所有可能的 k-link s-to 中具有最小的边权重总和-t G 中的路径。

设计一个O(k(m+ n)) 时间算法来计算从 s 到 t 的 k-link 最短路径。

如果您对算法有任何帮助，我们将不胜感激。

Answer 1

让 dp[amount][currentVertex] 给出 G 中从 s 开始到 currentVertex 并且包含 amount 的最短路径的长度 边。

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]

上面的算法会给出 G 中从 s 到 t 的 k-link 最短路径的长度。它的时间复杂度主要由循环 (1) 的复杂度决定。循环 (1) 单独具有复杂度 O(k)，而其内部部分 - (2) 只是遍历图形。如果使用邻接表，(2) 可以在 O(n+m) 中实现。因此整体复杂度为 O(k*(n+m))。

但是，这只会给你路径的长度，而不是路径本身。您可以通过为 dp[][] 的每个值存储前一个顶点来修改此算法。因此，每当您将 dp[pathLength+1][u] 的值设置为 dp[pathLength][vertex] + cost(vertex, u) 的值时一些变量 vertex, u, pathLength 你会知道之前使用的顶点是 vertex。因此，您可以将其存储为 prev[pathLength+1][u] = vertex。

之后就可以得到你想要的路径了。这个想法是通过使用您在 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存储的是G中s到t的k-link最短路径。