Algorytm
Przez s oznaczamy daszek źródłowy, w(i,j) to waga krawędzi (i,j) w grafie.
- Stwórz tablicę d odległości od czasu źródła na rzecz wszystkich wierzchołków grafu. na początku d[s] = 0, a d[v] = nieskończoność na rzecz wszystkich pozostałych wierzchołków.
- Utwórz kolejkę priorytetową Q wszystkich wierzchołków grafu. Priorytetem kolejki jest aktualnie wyliczona odległość.
- Dopóki rząd nie jest pusta:
- Usuń spośród kolejki daszek u o najniższym priorytecie (wierzchołek przyległy źródła, który nie został jeszcze rozważony)
- Dla każdego sąsiada v wierzchołka u dokonaj relaksacji przez u: o ile d[u] + w(u,v) < d[v] (poprzez u da się osiągnąć cel aż do v szybciej niż dotychczasową ścieżką), to d[v]: = d[u] + w(u,v).
Na końcu tablica d zawiera najkrótsze odległości aż do wszystkich wierzchołków.
Dodatkowo, możemy w tablicy poprzednik zapisywać na rzecz każdego wierzchołka numer jego bezpośredniego poprzednika na najkrótszej ścieżce, co pozwoli na odtworzenie pełnej ścieżki od czasu źródła aż do każdego wierzchołka - w stosunku do każdej relaksacji w ostatnim punkcie, u staje się poprzednikiem v.