Дейкстр в 2D массив Временной сложность

Question

Я просто интересен, о время сложности Дейкстра в 2D

Я знал, что Дейкстр с бинарным отвалом O (ElogV)

, но если мы имеем п-по -n массив 2D, и каждый узел в массиве содержит вершину (x, y, вес) и

он может идти в течение четырех направлений. Вверх, вниз, влево, вправо

поэтому общая вершина n^2 и край около 4 (n^2). Например, если вершина находится в < 1, 2>, то мы должны смотреть на четыре стороны < 0, 2> < 2, 2> < 1, 1> < 1, 3>

так, что, если мы запустим алгоритм в 2D, то временная сложность будет

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

Это право?

Я долго отвечаю ... Спасибо, что прочитали это.

Answer 1

Если расстояние между каждыми двумя узлами всегда одно и то же, то в этом случае алгоритм Дейкстры становится простой BFS. Вам вообще не нужна структура кучи. Сложность составляет O(n^2).

В противном случае сложность заключается в том, что вы показали O(n^2 log n).