我试图在无向加权图中找到2个顶点之间的最短路径 . 还已知权重是小于log（log | V |）的整数，其中| V |是顶点的数量 . 使用Bellman-Ford或Dijkstra算法很容易解决，但有没有哪种算法可以更快地完成？
到目前为止，我一直在考虑使用BFS并将重量大于1的边缘分成重量为1的几个，但是如果| V |则不是很好 . 数量很大 . 不，这不是我的功课，我只是想知道 .
考虑这个问题的一种方法是改善使用Dijkstra算法在无向加权图中找到两个顶点之间的最短路径的运行时间 . 因此，在这种情况下，您可以使用二进制堆作为数据结构 . 堆是具有heap属性的完整二叉树，每个父节点比最小堆（最大堆）中的树中的子节点小（大） . 在这里，您可以使用最小堆来存储起始节点中每个节点的开销 .
有关堆的更多信息，请访问：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次来检查邻居并且改变成本） .
希望这有帮助 .
1 回答
考虑这个问题的一种方法是改善使用Dijkstra算法在无向加权图中找到两个顶点之间的最短路径的运行时间 . 因此，在这种情况下，您可以使用二进制堆作为数据结构 . 堆是具有heap属性的完整二叉树，每个父节点比最小堆（最大堆）中的树中的子节点小（大） . 在这里，您可以使用最小堆来存储起始节点中每个节点的开销 .
有关堆的更多信息，请访问：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次来检查邻居并且改变成本） .
希望这有帮助 .