algorithm - 正加权有向无环图中的 k 边最短路径

Question

我有一个图 G = (V, E)，它是正加权的、有向的和无环的。我要设计一个在 O(k(m + n)) 中运行的算法，用于报告从 s 到 t 的 k 边最短路径。一条 k 边最短路径被定义为一条从 s 到 t 有 k 条边的路径，并且对于从 s 到 t 的所有路径，该路径的总权重也必须是最小的。

由于 BFS 不能单独用于寻找最短路径(除非权重相等)，我认为运行时间意味着使用 BFS 寻找具有 k 条边的路径。让我失望的是 k，因为我认为它意味着执行 BFS k 次。

我可能的想法是从源运行 BFS 以找到所有可能的 k-link 路径。通过跟踪沿途的级别并在我将每个节点添加到我的队列时存储每个节点的总路径权重，我可以找到所有可能的 k-link 路径及其权重。显然，如果我遇到路径权重较低的较低级别的目的地，则根据定义不存在 k 边最短路径。如果路径的总权重超过 k 条边，情况会怎样？它也不是 O(k(m + n))。任何有用的提示将不胜感激。

Answer 1

设f[i][j]是从s到j的i-link最短路径，最初我们有

f[1][x] = e(s, x);

然后迭代 K - 1 次，每一轮我们使用 f[i][] 来计算 f[i + 1][]，这可以通过

for each node v:
    f[i + 1][v] = INF;
for each edge e[u][v]:
    f[i + 1][v] = min(f[i + 1][v], f[i][u] + e[u][v]);

因此需要 O(k(n + m))。