单源最短路径问题的算法

Question

我们得到一个有向图 G = (V, E)，有正边和负边​​权重，但没有环。设 s ∈ V 为给定的源顶点。如何找到一种算法，找到所有顶点与 s 的距离，据推测运行速度比 Bellman Ford 的 O(VE) 时间复杂度更快。

Answer 1

如果图没有环，那么你可以按拓扑顺序处理顶点。

对于每个顶点 v，如果它可以从 s 到达 d，然后对于权重为 w 的每条边 (v,u)，将 u 标记为权重可达 d+w。如果 u 已经可以在较低的权重下达到，则不要管它。

因为你按拓扑顺序处理图，你知道当你处理一个顶点v时，你已经处理了它的所有前辈，所以你会知道的长度它从 s 开始的最短路径。第一个可达的顶点当然是 s.

在从 s.

可达的顶点子图上，很容易将它与 Kahn's algorithm 结合起来进行拓扑排序

1. 首先进行 BFS 搜索以找到从 s 可达的所有顶点，并同时计算该子集中每个顶点的传入边。
2. s 将是唯一计数为“0”的顶点。它与 s 的距离也已知为 0。将其放入队列中。
3. 当队列中有顶点时：
   1. 从队列中删除顶点 v
   2. 调整与邻居的距离
   3. 减少其邻居的传入边数。如果任何邻居的计数变为 0，则将其放入队列中。

完成后，将处理所有可到达的顶点，并且它们的所有距离都将已知。