Dijkstra算法在二维数组时间复杂度

Question

我只是在2D

想知道时间Dijkstra算法的复杂性，我知道的Dijkstra用二元堆是O（ElogV）

，但如果我们有一个正由-n数组2D，并且数组中的每个节点呈现顶点（x，y，weight）并且它可以沿着四个方向前进。上，下，左，右

因此，总顶点为n^2，边缘约为4（n^2）。例如，如果顶点是在< 1,2>那么我们必须寻找四个侧< 0,2> < 2,2> < 1,1> < 1,3>

这样，如果我们运行2D中的算法然后是时间复杂度将是：

→ElogV→4（n^2）logn^2→8（n^2）logn_ = n^2logn。

是这样的吗？

我很长的答案..谢谢你阅读此。

Answer 1

如果每两个节点之间的距离总是相同，那么在这种情况下，Dijkstra算法就变成了一个简单的BFS。你根本不需要堆结构。复杂度为O(n^2)。

否则复杂程度如您所示O(n^2 log n)。