二维数组中的 Dijkstra 时间复杂度
Dijkstra in 2-D array Time complexity
我只是想知道二维中 Dijkstra 的时间复杂度
我知道二叉堆的 Dijkstra 是 O(ElogV)
但是如果我们有一个 n×n 二维数组并且数组中的每个节点都表示顶点 (x, y, weight) 并且
它可以去四个方向。上、下、左、右
因此，总顶点为 n^2，边约为 4(n^2)。例如，如果顶点在 <1, 2> 中，那么我们必须寻找四个边 <0, 2> <2, 2> <1, 1> <1, 3>
因此，如果我们 运行 二维算法，那么时间复杂度将为
-> ElogV -> 4(n^2) log n^2 -> 8(n^2)logn ~= n^2 log n.
这样对吗？
我很期待答案。感谢您阅读本文。
如果每两个节点之间的距离总是相同的，那么Dijkstra算法就变成了一个简单的BFS。您根本不需要堆结构。复杂度为 O(n^2).
否则复杂度如您所示O(n^2 log n)。
我只是想知道二维中 Dijkstra 的时间复杂度
我知道二叉堆的 Dijkstra 是 O(ElogV)
但是如果我们有一个 n×n 二维数组并且数组中的每个节点都表示顶点 (x, y, weight) 并且
它可以去四个方向。上、下、左、右
因此，总顶点为 n^2，边约为 4(n^2)。例如，如果顶点在 <1, 2> 中，那么我们必须寻找四个边 <0, 2> <2, 2> <1, 1> <1, 3>
因此，如果我们 运行 二维算法，那么时间复杂度将为
-> ElogV -> 4(n^2) log n^2 -> 8(n^2)logn ~= n^2 log n.
这样对吗？
我很期待答案。感谢您阅读本文。
如果每两个节点之间的距离总是相同的，那么Dijkstra算法就变成了一个简单的BFS。您根本不需要堆结构。复杂度为 O(n^2).
否则复杂度如您所示O(n^2 log n)。