正加权有向无环图中的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链路路径。通过跟踪沿途的级别，并在将每个节点添加到队列中时将总路径权重存储到每个节点，我可以找到所有可能的k链路路径及其权重。显然，如果我遇到路径权重较低的较低级别的目的地，根据定义就没有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))。