Następnie musimy uwzględnić fakt, że najkrótsza ścieżka do jakiegoś wierzchołka po wierzchołkach z nowego zbioru może teraz zawierać wierzchołek Ale wtedy musi on być ostatnim na niej wierzchołkiem (do każdego innego dałoby się dojść krócej, nie używając ), a zatem jej długość równa jest i zostanie prawidłowo obliczona w następnym kroku algorytmu.
Złożoność Złożoność obliczeniowa algorytmu Dijkstry zależy od liczby wierzchołków i krawędzi grafu. O rzędzie złożoności decyduje implementacja kolejki priorytetowej: wykorzystując „naiwną” implementację poprzez zwykłą tablicę, otrzymujemy algorytm o złożoności w implementacji kolejki poprzez kopiec złożoność wynosi po zastąpieniu zwykłego kopca kopcem Fibonacciego złożoność zmienia się na
Pierwszy wariant jest optymalny dla grafów gęstych (czyli jeśli ), drugi jest szybszy dla grafów rzadkich trzeci jest bardzo rzadko używany ze względu na duży stopień skomplikowania i niewielki w porównaniu z nim zysk czasowy.
Problemy i algorytmy pokrewne Algorytm Dijkstry nie działa, jeśli w grafie występują krawędzie z ujemnymi wagami – w tym wypadku używa się wolniejszego, lecz bardziej ogólnego algorytmu Bellmana-Forda.