Почему временная сложность алгоритма Дейкстраса O (V ^ 2)

Question

Я только что прочитал статью об алгоритме Дейкстраса в Википедии, там же сказано, что временная сложность равна O(V^2). Моя проблема в том, что я не могу себе это объяснить.

Может кто-нибудь мне это объяснить?

Answer 1

Решение O(V^2) с использованием массива такое же, как «обычное» решение (очередь с приоритетом), но вместо него используется массив с открытыми расстояниями и поиск в нем вместо поиска в куче.

open_nodes = [inf, inf, inf, ..., inf]
d = [inf, inf, inf, ..., inf]
open_nodes[source] = 0
while d[target] == inf:
  v = argmin(open_nodes)  // O(V)
  d[v] = open_nodes[v]
  for each u such that (v,u) is an edge:
    if d[u] != inf:
      // relaxation:
      open_nodes[u] = min(open_nodes[u], d[v] + w(v,u))
    // close v
  open_nodes[v] = inf

• l oop повторяется не более |V| раз, поскольку вы закрываете узел на каждой итерации и никогда не открываете его повторно.
• argmin - это O(|V|). По сути, это поиск минимума в несортированном массиве.
• релаксация занимает O (1) и повторяется не более O(|E|) раз, так как вы вызываете ее не более одного раза для каждого исходящего ребра.

Это дает нам всего O(|V|^2 + |E|), но, поскольку |E| <= |V|^2, это просто O(|V|^2)