Dijkstra in 2-D array Time complexity

Question

I am just wondering about Time complexity of Dijkstra in 2D

I knew that Dijkstra with Binary Heap is O(ElogV)

but if we have a n-by-n array 2D and each node in the array present the vertex (x, y, weight) and

it can go for four direction. Up, down, left, right

therefore, total vertex is n^2 and edge is about 4(n^2). For example, if vertex is in <1, 2> then we have to look for four side <0, 2> <2, 2> <1, 1> <1, 3>

so that, if we run the algorithm in 2D then time complexity will be

-> ElogV -> 4(n^2) log n^2 -> 8(n^2)logn ~= n^2 log n.

is this right?

I am long for the answer.. Thank you for reading this.

Answer 1

If the distance between every two nodes is always the same, then in that case the Dijkstra's algorithm becomes a simple BFS. You don't need a heap structure at all. The complexity is O(n^2).

Otherwise the complexity is as you showed O(n^2 log n).