Алгоритм Дейкстры Runtime

Question

Я знаю, что это может быть не очень хороший вопрос, но мне было интересно, как это время исполнения O (ElogV).

Вот Algo

DIJKSTRA(G,w,s) 
S=null 
PQ=G.V 
while (PQ!=null) 
    u=Extract-Min(PQ) 
    S=S+u \\Add node u to set S(explored vertices) 
    foreach (v in adj(u)) 
     if(d(v) > d(u) + w(u,v)) 
      d(v) = d(u) + w(u,v) \\at this step, we need to update the priority d(v) of vertex (v) in the Priority Queue. 

сложность времени задается O (E logV), а внутренний цикл выполняется в большинстве случаев E, и для каждой итерации цикла, оно принимает O (logV) время для обновления приоритет d (v) вершин (v) в очереди приоритетов PQ. Но эта операция требует от нас поиска вершины (v) в Priority Queue PQ, которая принимает O (v) время. Итак, как сложность времени O (E logV).

--Edit-- Если факт цикла while выполняется V раз и каждый раз, когда элемент извлекается из PQ, это означает, что время работы O (V logV), правильно?

Answer 1

Вам не нужно искать v в очереди приоритетов. Когда вы вставляете в очередь приоритетов, вы можете сохранить ссылку на вставленный узел в массиве, индексированном v, и посмотреть его мгновенно.