algorithm - 无向加权图中2个顶点之间的最短路径

Question

我试图在无向加权图中找到 2 个顶点之间的最短路径。众所周知，权重是小于 log(log|V|) 的整数，其中 |V|是顶点的数量。使用 Bellman-Ford 或 Dijkstra 算法很容易解决，但有没有更快的算法？

到目前为止，我一直在考虑使用 BFS 并将权重大于 1 的边分成几个权重为 1 的边，但是如果 |V| 并不是一个好主意是大数。不，这不是我的作业，我只是想知道。

Answer 1

思考这个问题的一种方法是提高使用 Dijkstra 算法寻找无向加权图中两个顶点之间的最短路径的运行时间。所以在这种情况下，您可以使用二叉堆作为数据结构。堆是一个完全二叉树，其堆属性是每个父节点都小于(大于)最小堆(最大堆)中树中的子节点。这里可以使用最小堆来存储从起始节点到每个节点的成本。

有关堆的更多信息可以在这里找到:https://courses.csail.mit.edu/6.006/fall10/handouts/recitation10-8.pdf

有了堆，Dijkstra 算法的运行时间可以从 O(V^2) 减少到 O(E log E)，因为从堆中选择最小距离需要 O(log V)(移除最小距离是 O(1)，修复堆需要 O(log V))，更新到顶点的距离总共需要 O(E log V)(修复堆需要 O(log V)，检查邻居和更改成本需要 E 次).

希望这对您有所帮助。