Pseudokod Dijkstra(G,w,s): dla każdego wierzchołka v w V[G] wykonaj d[v] := nieskończoność poprzednik[v] := niezdefiniowane d[s] := 0 Q := V dopóki Q niepuste wykonaj u := Zdejmij_Min(Q) dla każdego wierzchołka v – sąsiada u wykonaj jeżeli d[v] > d[u] + w(u, v) to d[v] := d[u] + w(u, v) poprzednik[v] := u
Wyświetl("Droga wynosi: " + d[v])
Dowód poprawności Oznaczmy przez zbiór wierzchołków, które zostały już zdjęte z kolejki. Dowód opiera się na następujących dwóch faktach (niezmiennikach), prawdziwych przez cały czas trwania algorytmu: Dla każdego wierzchołka liczba jest długością najkrótszej ścieżki od do Dla każdego wierzchołka jest długością najkrótszej ścieżki do prowadzącej tylko przez wierzchołki z
Na początku oba fakty są oczywiste ( jest zbiorem pustym). Przy zdejmowaniu wierzchołka z kolejki wiemy, na podstawie faktu 2, że nie da się do niego dojść żadną krótszą drogą przez wierzchołki z Z drugiej strony, ponieważ ma najniższy priorytet, przejście przez jakikolwiek inny wierzchołek spoza dałoby od razu co najmniej tak samo długą ścieżkę. A zatem dołączając wierzchołek do zachowujemy prawdziwość faktu 1.