1

我得到一个图，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))。任何有用的提示将不胜感激。

4

1 回答 1

4

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

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)).

于 2013-03-14T01:31:46.587 回答