正加权有向无环图的边最短路径

我给出了一个图，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））。 任何有用的提示，将不胜感激。

---

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

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

链接地址: http://www.djcxy.com/p/35279.html

上一篇: Edge Shortest Path in Positive Weighted Directed Acyclic Graph

下一篇: Maximum weight connected subgraph in an directed acyclic graph