Какова временная сложность алгоритма Дейкстры

Question

Dijkstra((V, E)):
  S = {}    //O(1)
  for each vertex v ∈ V:    //O(V)
    d[v] = ∞    //O(1)
  d[source] = 0    //O(1)
  while S != V:    //O(V)
    v = non visited vertex with the smallest d[v]    //O(V)
    for each edge (v, u):    //O(E)
      if u ∈/ S and d[v] + w(v, u) < d[u]:
        d[u] = d[v] + w(v, u)
    S = S ∪ {v}

Примечание: ∈ / означает не в, я не могу набрать его в коде.

Этот вопрос может дублироваться с некоторыми сообщениями.

Понимание вычисления сложности времени для алгоритма Дейкстры

Сложность алгоритма Дейкстры

Сложность в алгоритме Дейкстры

Я читаю их и даже некоторые посты на Quora, но до сих пор не могу понять.Я поместил некоторые комментарии в псевдокоде и попытался решить это.Я действительно путаю, почему это O (E log V)

Answer 1

это O ((V logV) + (E logV)) = O (logV * (V + E)) для общих графиков.

Вы бы не просто предположили, что граф плотный, т.е. | E |= O (| V | ^ 2), так как большинство графов в приложениях фактически разрежены, т.е. | E |= O (| V |).

Answer 2

"Не посещенная вершина с наименьшим d [v]" фактически равна O (1), если вы используете min кучу , а вставка в минимальную кучу равна O (log V).

Поэтому сложность такая, как вы правильно упомянули для других циклов:

  O((V logV) + (E logV)) = O(E logV) // Assuming E > V which is reasonable