Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2026 mgr Jerzy Wałaszek

Najkrótsza ścieżka w grafie ważonym
Algorytm Dijkstry

SPIS TREŚCI

Problem

W spójnym grafie ważonym znaleźć najkrótsze ścieżki od wybranego wierzchołka startowego do wszystkich pozostałych wierzchołków.

Rozwiązanie

Jednym z podstawowych problemów w teorii grafów jest znajdowanie połączeń pomiędzy dwoma wybranymi wierzchołkami. Ścieżką (ang. path) nazywamy uporządkowany zbiór wierzchołków, które musimy kolejno przejść, aby dotrzeć w grafie od jednego \ wybranego wierzchołka do innego wybranego wierzchołka. Ścieżek takich może być kilka (lub może nie istnieć żadna – wtedy wierzchołki nazywamy izolowanymi).

obrazek Od wierzchołka 0 do wierzchołka 4
można dojść wieloma różnymi
ścieżkami:

ścieżka nr 1:  0 – 3 – 4
ścieżka nr 2:  0 – 1 – 3 –  4
ścieżka nr 3:  0 – 1 – 2 –  3 – 4
ścieżka nr 4:  0 – 1 – 2 –  4

Jeśli z krawędziami grafu związane są wagi, to każda ze ścieżek posiada swój koszt przejścia równy sumie wag krawędzi łączących poszczególne wierzchołki ścieżki. Dla podanego wyżej grafu ścieżki od wierzchołka 0 do 4 mają następujący koszt:

ścieżka nr 1-koszt = 3+3 = 6
ścieżka nr 2-koszt = 3 + 6+3 = 12
ścieżka nr 3-koszt = 3+1+5+3 = 12
ścieżka nr 4-koszt = 3+1+1 = 5

Przez najkrótszą ścieżkę (ang. shortest path) łączącą w grafie dwa wybrane wierzchołki będziemy rozumieli ścieżkę o najmniejszym koszcie przejścia, czyli o najmniejszej sumie wag tworzących tę ścieżkę krawędzi.

obrazek Od wierzchołka 0 do wierzchołka 4
najkrótszą ścieżką jest

ścieżka nr 1:  0 – 3 – 4
ścieżka nr 2:  0 – 1 – 3 – 4
ścieżka nr 3:  0 – 1 – 2 – 3 – 4
ścieżka nr 4:  0 – 1 – 2 – 4

o koszcie przejścia równym 5.

Jeśli wagi krawędzi są nieujemne, to problem znalezienia ścieżki o najniższym koszcie dojścia elegancko rozwiązuje algorytm Dijkstry. Algorytm ten pozwala znaleźć koszty dojścia od wierzchołka startowego v do każdego innego wierzchołka w grafie (o ile istnieje odpowiednia ścieżka). Dodatkowo wyznacza on poszczególne ścieżki. Zasada pracy jest następująca:

Tworzymy dwa zbiory wierzchołków Q i S. Początkowo zbiór Q zawiera wszystkie wierzchołki grafu, a zbiór S jest pusty. Dla wszystkich wierzchołków u grafu za wyjątkiem startowego v ustawiamy koszt dojścia d(u) na nieskończoność. Koszt dojścia d(v) zerujemy. Dodatkowo ustawiamy poprzednik p(u) każdego wierzchołka u grafu na niezdefiniowany. Poprzedniki będą wyznaczały w kierunku odwrotnym najkrótsze ścieżki od wierzchołków u do wierzchołka startowego v. Teraz w pętli dopóki zbiór Q zawiera wierzchołki, wykonujemy następujące czynności:
  1. Wybieramy ze zbioru Q wierzchołek u o najmniejszym koszcie dojścia d(u).
  2. Wybrany wierzchołek u usuwamy ze zbioru Q i dodajemy do zbioru S.
  3. Dla każdego sąsiada w wierzchołka u, który jest wciąż w zbiorze Q, sprawdzamy, czy
    d(w) > d(u)+waga krawędzi u – w.
    Jeśli tak, to wyznaczamy nowy koszt dojścia do wierzchołka w jako:
    d(w) ← d(u)+waga krawędzi u – w.
    Następnie wierzchołek u czynimy poprzednikiem w:
    p(w) ← u.

Aby lepiej zrozumieć zasadę działania algorytmu Dijkstry, prześledźmy jego kolejne kroki w poniższej tabelce:

obrazek   Mamy ważony graf skierowany
z wierzchołkiem startowym v = 0.
Będziemy wyznaczać najniższe koszty dojścia
od wyróżnionego wierzchołka do wszystkich
pozostałych wierzchołków w grafie oraz
najkrótsze ścieżki pomiędzy wyróżnionym
wierzchołkiem, a wszystkimi pozostałymi.
obrazek   Tworzymy dwa zbiory S i Q. Zbiór S jest
początkowo pusty, a zbiór Q obejmuje
wszystkie wierzchołki grafu.
W zbiorze S znajdą się wierzchołki
przetworzone przez algorytm Dijkstry,
a w zbiorze Q będą wierzchołki wciąż
czekające na przetworzenie.
obrazek
u 0 1 2 3 4 5
d[u] 0 ∞ ∞ ∞ ∞ ∞
p[u] -1 -1 -1 -1 -1 -1
Tworzymy dwie tablice d i p
o n elementach, gdzie n oznacza liczbę
wierzchołków w grafie. Elementy tablicy d
będą zawierały minimalne koszty dojścia
do poszczególnych wierzchołków z wierzchołka
startowego.
Początkowo w elementach d umieszczamy
wartość +nieskończoność. W elemencie d[v]
umieszczamy zero. Elementy tablicy p będą
przechowywały numery wierzchołków
poprzedników na ścieżce od wierzchołka v. Idąc
wstecz po tych numerach dotrzemy
do wierzchołka startowego. We wszystkich
elementach tablicy p umieszczamy wartość,
która nie może oznaczać numeru wierzchołka,
np. -1.
 obrazek
u 0 1 2 3 4 5
d[u] 0 3 ∞ ∞ 3 ∞
p[u] -1  0 -1 -1  0 -1
W zbiorze Q szukamy wierzchołka u
o najmniejszym koszcie dojścia d[u].
Oczywiście, jest to wierzchołek startowy 0,
dla którego d[0] = 0. Wierzchołek 0 przenosimy
ze zbioru Q do S. Następnie przeglądamy
wszystkich sąsiadów przeniesionego wierzchołka
– tutaj są to wierzchołki 1 i 4. Sprawdzamy, czy:
d[1] > d[0] + 3 ? – TAK, zatem
d[1] ← d[0]+3 = 3. Do p[1] wpisujemy 0,
czyli poprzednik na ścieżce.
d[4] > d[0]+3 ? – TAK, zatem
d[4] ← d[0]+3 = 3. Do p[4] wpisujemy 0,
czyli poprzednik na ścieżce.
 obrazek
u 0 1 2 3 4 5
d[u] 0 3 4 ∞ 3 ∞
p[u] -1  0  1 -1  0 -1
Ponownie w zbiorze Q szukamy wierzchołka u
o najmniejszym koszcie dojścia d[u]. Są dwa
takie wierzchołki: 1 i 4 (d[1] = 3 i d[4] = 3).
Wybieramy dowolny z nich, niech będzie to
wierzchołek 1. Przenosimy go do zbioru S
i sprawdzamy sąsiada 2:
d[2] > d[1]+1 ? – TAK, zatem
d[2] ← d[1]+1 = 4. Do p[2] wpisujemy 1, czyli
poprzednik na ścieżce.
obrazek
u 0 1 2 3 4 5
d[u] 0 3 4 ∞ 3 5
p[u] -1  0  1 -1  0 4
Kolejnym wierzchołkiem u w zbiorze Q
o najniższym koszcie dojścia d[u] jest
wierzchołek 4 (d[4] = 3). Przenosimy go
do zbioru S, a następnie sprawdzamy
koszt dojścia do jego sąsiada, wierzchołka 5:
d[5] > d[4]+2 ? – TAK, zatem
d[5] ← d[4]+2 = 5. Do p[5] wpisujemy 4, czyli
poprzednik na ścieżce.
obrazek
u 0 1 2 3 4 5
d[u] 0 3 4 7 3 5
p[u] -1  0  1  2  0 4
Teraz ze zbioru Q przenosimy do S
wierzchołek 2 (d[2] = 4). Wierzchołek ten
posiada w zbiorze Q dwóch sąsiadów: 3 i 5.
Sprawdzamy ich koszty dojścia:
d[3] > d[2]+3 ? – TAK, zatem
d[3] ← d[2]+3 = 7. Do p[3] wpisujemy 2, czyli
poprzednik na ścieżce.
d[5] > d[2]+1 ? – NIE, nic dalej nie robimy z tym
wierzchołkiem
obrazek
u 0 1 2 3 4 5
d[u] 0 3 4 6 3 5
p[u] -1  0  1  5  0 4
Do zbioru S przenosimy wierzchołek 5
(d [5] = 5). W zbiorze Q ma on tylko jednego
sąsiada, wierzchołek 3. Sprawdzamy koszt
dojścia do wierzchołka 3:
d[3] > d[5]+1 ? – TAK, zatem
d[3] ← d[5]+1 = 6. Do p[3] wpisujemy 5, czyli
poprzednik na ścieżce.
Zwróć uwagę, że w tym przypadku algorytm
znalazł lepszą ścieżkę do wierzchołka 3
o niższym koszcie.
obrazek
u 0 1 2 3 4 5
d[u] 0 3 4 6 3 5
p[u] -1  0  1  5  0 4
Do zbioru S przenosimy ostatni wierzchołek 3.
Zbiór Q stał się pusty, zatem przeniesiony
wierzchołek nie ma w zbiorze Q żadnych
sąsiadów. Algorytm kończy się. W tablicy d
mamy policzone koszty dojścia do każdego
z wierzchołków grafu. W tablicy p znajdują się
poprzedniki na ścieżce każdego wierzchołka,
co pozwala odtworzyć ścieżki do poszczególnych
wierzchołków grafu: idziemy wstecz po kolejnych
poprzednikach, aż dojdziemy do wierzchołka
startowego, dla którego nie istnieje poprzednik
(wartość -1).

Z tablic d i p odczytujemy:

Algorytm Dijkstry obliczania najkrótszych ścieżek i kosztów dojścia w grafie ważonym – wersja poglądowa

Wejście:

n : liczba wierzchołków w grafie; n ∈ C.
graf : zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Definicja grafu powinna udostępniać wagi krawędzi.
v : wierzchołek startowy; v ∈ C.

Wyjście:

d : n elementowa tablica z kosztami dojścia od wierzchołka v do wierzchołka i-tego wzdłuż najkrótszej ścieżki. Koszt dojścia jest sumą wag krawędzi, przez które przechodzimy posuwając się wzdłuż wyznaczonej najkrótszej ścieżki.
p : n elementowa tablica z poprzednikami wierzchołków na wyznaczonej najkrótszej ścieżce. Dla i-tego wierzchołka grafu p[i] zawiera numer wierzchołka poprzedzającego na najkrótszej ścieżce

Elementy pomocnicze:

S : zbiór wierzchołków grafu o policzonych już najkrótszych ścieżkach od wybranego wierzchołka v.
Q : zbiór wierzchołków grafu, dla których najkrótsze ścieżki nie zostały jeszcze policzone.
u,w : wierzchołki; u,w ∈ C.

Lista kroków:

K01: S ← Ø ; zbiór S tworzymy jako pusty
K02: Q ← wszystkie wierzchołki grafu
K03: Utwórz n elementową tablicę d ; tablica na koszty dojścia
K04: Utwórz n elementową tablicę p ; tablica poprzedników na ścieżkach
K05: Tablicę d wypełnij największą wartością dodatnią
K06: d[v] ← 0 ; koszt dojścia do samego siebie jest zawsze zerowy
K07: Tablicę p wypełnij wartościami -1 ; -1 oznacza brak poprzednika
K08: Dopóki Q zawiera wierzchołki, 
     wykonuj kroki K09…K12
K09: Z Q do S przenieś wierzchołek u o najmniejszym d[u]
K10: Dla każdego sąsiada w wierzchołka u: ; przeglądamy
     wykonuj kroki K11…K12 ; sąsiadów przeniesionego wierzchołka
K11:   Jeśli w nie jest w Q, ; szukamy sąsiadów obecnych w Q
       to następny obieg pętli K10
K12:   Jeśli d[w] > d[u]+waga krawędzi u–w, 
       to: ; sprawdzamy koszt dojścia.
       d[w] ← d[u]+waga krawędzi u–w ; Jeśli mamy niższy,
       p[w] ← u ; to modyfikujemy koszt i zmieniamy poprzednika w na u
K13: Zakończ

Aby efektywnie zaimplementować algorytm Dijkstry, musimy najpierw rozwiązać kilka problemów.

Pierwszym z nich jest sposób reprezentacji grafu w pamięci komputera. Ponieważ algorytm często będzie odwoływał się do wierzchołków sąsiadujących z wierzchołkiem przetwarzanym (tzn. połączonych z nim krawędzią), to reprezentacja grafu powinna efektywnie umożliwiać szybkie wyszukiwanie sąsiadów. Warunek ten spełniają listy sąsiedztwa.

Drugim problemem jest sposób reprezentacji zbiorów  S i Q. Zbiory te są ze sobą powiązane logicznie. Jeśli wierzchołek jest w zbiorze Q, to oczywiście nie ma go w zbiorze S i na odwrót. Utworzymy zatem dodatkową tablicę logiczną QS[ ] o n-elementach. Indeks będzie określał wierzchołek grafu, natomiast zawartość false będzie oznaczała, iż wierzchołek ten jest w Q, a zawartość true, iż jest w S.

Następny problem, to sprawdzanie, czy zbiór Q jest pusty w warunku kontynuacji pętli. Zwróć uwagę, iż przy każdym przebiegu tej pętli dokładnie jeden wierzchołek jest przenoszony z Q do S (zmienia swój stan w QS[ ] z false na true). Zatem po n-tym przebiegu wszystkie wierzchołki automatycznie znajdą się w zbiorze S. Nie musimy sprawdzać Q – wystarczy, iż pętlę tą zrealizujemy jako pętlę iteracyjną o n przebiegach.

Kolejnym problemem wpływającym na efektywność algorytmu jest wyszukiwanie w zbiorze Q wierzchołka o najmniejszej wartości kosztu dojścia d. Możemy tutaj zastosować proste wyszukiwanie liniowe – wtedy cały algorytm będzie miał czasową złożoność obliczeniową klasy O(n2). Jednakże dużo lepszym pomysłem (ale trudniejszym w realizacji) jest zastosowanie kolejki priorytetowej opartej na strukturze kopca.

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.
Poniższy program jest przykładową realizacją algorytmu Dijkstry z wyszukiwaniem liniowym. Definicja danych wejściowych jest następująca:

W pierwszym wierszu program odczytuje kolejno numer wierzchołka startowego v, liczbę wierzchołków n oraz liczbę krawędzi m. W m kolejnych wierszach znajdują się definicje krawędzi. Definicja składa się z trzech liczb x, y, w. Pierwsza i druga liczba określa wierzchołki grafu, które są ze sobą połączone tą krawędzią – krawędź biegnie od wierzchołka x do wierzchołka y. Trzecia liczba jest wagą krawędzi w.

Na wyjściu program wypisuje znalezione najkrótsze ścieżki od wierzchołka v do wszystkich pozostałych wierzchołków. Oprócz ścieżki wypisywany jest również koszt przejścia tej ścieżki.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):
obrazek 0 6 9
0 1 3
0 4 3
1 2 1
2 3 3
2 5 1
3 1 3
4 5 2
5 0 6
5 3 1
Pascal
// Algorytm Dijkstry
// z wyszukiwaniem liniowym
// Data: 15.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program dijkstra;

// Typy danych
type
  PSLel = ^SLel;
  SLel =  record
    next : PSLel;
    // numer węzła docelowego
    // i waga krawędzi
    v, w : integer;
  end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  i,j,m,n,v,u,w,x,y,sptr : integer;
  d, p, S : array of integer;
  // Zbiory Q i S
  QS : array of boolean;
  // Tablica list sąsiedztwa
  graf: array of PSLel;
  pw, rw : PSLel;

begin
  // Węzeł startowy,
  // liczba wierzchołków
  // i krawędzi
  read(v, n, m);
  // Tworzymy
  // tablice dynamiczne
  //-------------------
  // Tablica kosztów dojścia
  SetLength(d, n);
  // Tablica poprzedników
  SetLength(p, n);
  // Zbiory Q i S
  SetLength(QS, n);
  // Tablica list sąsiedztwa
  SetLength(graf, n);
  // Stos
  SetLength(S, n);
  // Wskaźnik stosu
  sptr := 0;
  // Inicjujemy
  // tablice dynamiczne
  for i := 0 to n-1 do
  begin
    d[i] := MAXINT;
    p[i] := -1;
    QS[i] := false;
    graf[i] := nil;
  end;
  // Odczytujemy
  // dane wejściowe
  for i := 1 to m do
  begin
    // Odczytujemy
    // krawędź z wagą
    read(x, y, w);
    // Tworzymy element
    // listy sąsiedztwa
    new(pw);
    // Wierzchołek
    // docelowy krawędzi
    pw^.v := y;
    // Waga krawędzi
    pw^.w := w;
    pw^.next := graf[x];
    // Element
    // dołączamy do listy
    graf[x] := pw;
  end;
  writeln;
  // Koszt dojścia v
  // jest zerowy
  d[v] := 0;
  // Wyznaczamy ścieżki
  for i := 1 to n do
  begin
    // Szukamy wierzchołka
    // w Q o najmniejszym
    // koszcie d
    j := 0;
    while QS[j] do inc(j);
    u := j;
    inc(j);
    while j < n do
    begin
      if not QS[j] and
         (d[j] < d[u]) then u := j;
      inc(j)
    end;
    // Znaleziony wierzchołek
    // przenosimy do S
    QS[u] := true;
    // Modyfikujemy odpowiednio
    // wszystkich sąsiadów u,
    // którzy są w Q
    pw := graf[u];
    while pw <> nil do
    begin
      if not QS[pw^.v] and
         (d[pw^.v] > d[u]+pw^.w) then
      begin
        d[pw^.v] := d[u]+pw^.w;
        p[pw^.v] := u;
      end;
      pw := pw^.next;
    end;
  end;
  // Gotowe, wyświetlamy wyniki
  for i := 0 to n-1 do
  begin
    write(i, ': ');
    // Ścieżkę przechodzimy
    // od końca ku początkowi,
    // zapisując na stosie
    // kolejne wierzchołki
    j := i;
    while j > -1 do
    begin
      S[sptr] := j;
      inc(sptr);
      j := p[j];
    end;
    // Wyświetlamy ścieżkę,
    // pobierając wierzchołki
    // ze stosu
    while sptr > 0 do
    begin
      dec(sptr);
      write(S [sptr], ' ');
    end;
    // Na końcu ścieżki
    // wypisujemy jej koszt
    writeln('$', d[i]);
  end;
  // Usuwamy
  // tablice dynamiczne
  SetLength(d, 0);
  SetLength(p, 0);
  SetLength(QS, 0);
  SetLength(S, 0);
  for i := 0 to n-1 do
  begin
    pw := graf[i];
    while pw <> nil do
    begin
      rw := pw;
      pw := pw^.next;
      dispose(rw);
    end;
  end;
  SetLength(graf, 0);
end.
C++
// Algorytm Dijkstry
// z wyszukiwaniem liniowym
// Data: 15.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// Typy danych
struct SLel
{
  SLel * next;
  // numer węzła docelowego
  // i waga krawędzi
  int v, w;
};

const int MAXINT = 2147483647;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int i, j, m, n, v, u, w, x, y;
  int sptr, *d, *p, *S;
  // Zbiory Q i S
  bool *QS;
  // Tablica list sąsiedztwa
  SLel **graf;
  SLel *pw, *rw;

  // Węzeł startowy,
  // liczba wierzchołków
  // i krawędzi
  cin >> v >> n >> m;
  // Tworzymy
  // tablice dynamiczne
  //-------------------
  // Tablica kosztów dojścia
  d = new int [n];
  // Tablica poprzedników
  p = new int [n];
  // Zbiory Q i S
  QS = new bool [n];
  // Tablica list sąsiedztwa
  graf = new SLel * [n];
  // Stos
  S = new int [n];
  // Wskaźnik stosu
  sptr = 0;
  // Inicjujemy
  // tablice dynamiczne
  for(i = 0; i < n; i++)
  {
    d[i] = MAXINT;
    p[i] = -1;
    QS[i] = false;
    graf[i] = nullptr;
  }
  // Odczytujemy
  // dane wejściowe
  for(i = 0; i < m; i++)
  {
    // Odczytujemy
    // krawędź z wagą
    cin >> x >> y >> w;
    // Tworzymy element
    // listy sąsiedztwa
    pw = new SLel;
    // Wierzchołek
    // docelowy krawędzi
    pw->v = y;
    // Waga krawędzi
    pw->w = w;
    pw->next = graf[x];
    // Element
    // dołączamy do listy
    graf[x] = pw;
  }
  cout << endl;
  // Koszt dojścia v
  // jest zerowy
  d[v] = 0;
  // Wyznaczamy ścieżki
  for(i = 0; i < n; i++)
  {
    // Szukamy wierzchołka w Q
    // o najmniejszym koszcie d
    for(j = 0; QS[j]; j++);
    for(u = j++; j < n; j++)
      if(!QS[j] && (d[j] < d[u]))
        u = j;
    // Znaleziony wierzchołek
    // przenosimy do S
    QS[u] = true;
    // Modyfikujemy odpowiednio
    // wszystkich sąsiadów u,
    // którzy są w Q
    for(pw = graf[u]; pw;
        pw = pw->next)
      if(!QS[pw->v] &&
         (d[pw->v] > d[u]+pw->w))
      {
        d[pw->v] = d[u]+pw->w;
        p[pw->v] = u;
      }
  }
  // Gotowe, wyświetlamy wyniki
  for(i = 0; i < n; i++)
  {
    cout << i << ": ";
    // Ścieżkę przechodzimy
    // od końca ku początkowi,
    // zapisując na stosie
    // kolejne wierzchołki
    for(j = i; j > -1; j = p[j])
      S[sptr++] = j;
    // Wyświetlamy ścieżkę,
    // pobierając wierzchołki
    // ze stosu
    while(sptr)
      cout << S[--sptr] << " ";
    // Na końcu ścieżki
    // wypisujemy jej koszt
    cout << "$" << d[i] << endl;
  }
  // Usuwamy
  // tablice dynamiczne
  delete [] d;
  delete [] p;
  delete [] QS;
  delete [] S;
  for(i = 0; i < n; i++)
  {
    pw = graf[i];
    while(pw)
    {
      rw = pw;
      pw = pw->next;
      delete rw;
    }
  }
  delete [] graf;
  return 0;
}
Basic
' Algorytm Dijkstry
' z wyszukiwaniem liniowym
' Data: 15.03.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Typy danych
Type SLel
  Dim As SLel Ptr Next
  ' numer węzła docelowego
  ' i waga krawędzi
  Dim As Integer v, w
End Type

const MAXINT = 2147483647

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer i, j, m, n, v, _
               u, w, x, y, sptr
Dim As Integer Ptr d, p, S
' Zbiory Q i S
Dim As Byte Ptr QS
' Tablica list sąsiedztwa
Dim As SLel Ptr Ptr graf
Dim As SLel Ptr pw, rw

Open Cons For Input As #1
' Węzeł startowy,
' liczba wierzchołków
' i krawędzi
Input #1, v, n, m
' Tworzymy
' tablice dynamiczne
'-------------------
' Tablica kosztów dojścia
d = New integer [n]
' Tablica poprzedników
p = New integer [n]
' Zbiory Q i S
QS = New Byte [n]
' Tablica list sąsiedztwa
graf = New SLel Ptr [n]
' Stos
S = New Integer [n]
' Wskaźnik stosu
sptr = 0
' Inicjujemy
' tablice dynamiczne
For i = 0 To n-1
  d[i] = MAXINT
  p[i] = -1
  QS[i] = 0
  graf[i] = 0
Next
' Odczytujemy
' dane wejściowe
For i = 0 To m-1
  ' Odczytujemy krawędź
  ' z wagą
  Input #1, x, y, w
  ' Tworzymy element
  ' listy sąsiedztwa
  pw = New SLel
  ' Wierzchołek
  ' docelowy krawędzi
  pw->v = y
  ' Waga krawędzi
  pw->w = w
  ' Element dołączamy
  ' do listy
  pw->next = graf[x]
  graf[x] = pw
Next
Close #1
Print
' Koszt dojścia v
' jest zerowy
d[v] = 0
' Wyznaczamy ścieżki
For i = 0 To n-1
  ' Szukamy wierzchołka w Q
  ' o najmniejszym koszcie d
  j = 0
  while QS[j] = 1
  	 j += 1
  Wend
  u = j
  j += 1
  While j < n
    If (QS[j] = 0) AndAlso _
       (d[j] < d[u]) Then u = j
    j += 1
  Wend
   ' Znaleziony wierzchołek
   ' przenosimy do S
  QS[u] = 1
  ' Modyfikujemy odpowiednio
  ' wszystkich sąsiadów u,
  ' którzy są w Q
  pw = graf[u]
  While pw <> 0
    If (QS[pw->v] = 0) AndAlso _
       (d[pw->v] > d[u]+pw->w) Then
      d[pw->v] = d[u]+pw->w
      p[pw->v] = u
    End If
    pw = pw->next
  Wend
Next
' Gotowe,
' wyświetlamy wyniki
For i = 0 To n-1
  Print i;":";
  ' Ścieżkę przechodzimy
  ' od końca ku początkowi, 
  ' zapisując na stosie
  ' kolejne wierzchołki
  j = i
  While j > -1
  	 S[sptr] = j
  	 sptr += 1
  	 j = p[j]
  Wend
  ' Wyświetlamy ścieżkę,
  ' pobierając wierzchołki
  ' ze stosu
  While sptr > 0
  	 sptr -= 1
  	 Print S[sptr];
  Wend
  ' Na końcu ścieżki
  ' wypisujemy jej koszt
  Print Using " $&";d[i]
Next
' Usuwamy
' tablice dynamiczne
Delete [] d
Delete [] p
Delete [] QS
Delete [] S
For i = 0 To n-1
  pw = graf[i]
  While pw
    rw = pw
    pw = pw->next
    Delete rw
  Wend
Next
Delete [] graf
End
Python (dodatek)
# Algorytm Dijkstry
# z wyszukiwaniem liniowym
# Data: 14.02.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Klasa listy
class SLel:
    def __init__(self):
        self.next = None
        # numer węzła docelowego
        # i waga krawędzi
        self.v = 0
        self.w = 0


MAXINT = 2147483647

# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Węzeł startowy,
# liczba wierzchołków
# i krawędzi
x = input().split()
v = int(x[0])
n = int(x[1])
m = int(x[2])
# Tworzymy
# tablice dynamiczne
#-------------------
# Tablica kosztów dojścia
d = [MAXINT] * n
# Tablica poprzedników
p = [-1] * n
# Zbiory Q i S
qs = [False] * n
# Tablica list sąsiedztwa
graf = [None] * n
# Stos
s = [0] * n
# Wskaźnik stosu
sptr = 0
# Odczytujemy
# dane wejściowe
for i in range(m):
    # Odczytujemy krawędź
    # z wagą
    z = input().split()
    x = int(z[0])
    y = int(z[1])
    w = int(z[2])
    # Tworzymy element
    # listy sąsiedztwa
    pw = SLel()
    # Wierzchołek
    # docelowy krawędzi
    pw.v = y
    # Waga krawędzi
    pw.w = w
    # Element dołączamy
    # do listy
    pw.next = graf[x]
    graf[x] = pw
print()
# Koszt dojścia v
# jest zerowy
d[v] = 0
# Wyznaczamy ścieżki
for i in range(n):
    # Szukamy wierzchołka w Q
    # o najmniejszym koszcie d
    j = 0
    while qs[j]:
        j += 1
    u = j
    j += 1
    while j < n:
        if (not qs[j]) and \
           (d[j] < d[u]):
            u = j
        j += 1
     # Znaleziony wierzchołek
     # przenosimy do S
    qs[u] = True
    # Modyfikujemy odpowiednio
    # wszystkich sąsiadów u,
    # którzy są w Q
    pw = graf[u]
    while pw:
        if (not qs[pw.v]) and \
           (d[pw.v] > d[u]+pw.w):
            d[pw.v] = d[u]+pw.w
            p[pw.v] = u
        pw = pw.next
# Gotowe,
# wyświetlamy wyniki
for i in range(n):
    print(i,":",sep="",end=" ")
    # Ścieżkę przechodzimy
    # od końca ku początkowi, 
    # zapisując na stosie
    # kolejne wierzchołki
    j = i
    while j > -1:
        s[sptr] = j
        sptr += 1
        j = p[j]
    # Wyświetlamy ścieżkę,
    # pobierając wierzchołki
    # ze stosu
    while sptr > 0:
        sptr -= 1
        print(s[sptr],end=" ")
    # Na końcu ścieżki
    # wypisujemy jej koszt
    print("$",d[i], sep="")
# Usuwamy
# tablice dynamiczne
del d,p,qs,s
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
del graf
Wynik:
0 6 9
0 1 3
0 4 3
1 2 1
2 3 3
2 5 1
3 1 3
4 5 2
5 0 6
5 3 1

0: 0 $0
1: 0 1 $3
2: 0 1 2 $4
3: 0 4 5 3 $6
4: 0 4 $3
5: 0 4 5 $5

Algorytm Dijkstry z kolejką priorytetową w postaci kopca - wersja poglądowa

Aby efektywnie wykorzystać kopiec w algorytmie Dijkstry znajdowania najkrótszych ścieżek w grafie, w elementach kopca zapamiętujemy numery wierzchołków grafu. Poprzez te numery możemy się prosto odwoływać do tablicy d przechowującej aktualne koszty dojścia do danego wierzchołka w grafie. Również wierzchołki grafu powinny pamiętać swoją pozycję w kopcu. Dzięki temu szybko odnajdziemy wierzchołek, którego koszt d został zmodyfikowany. Pozycję wierzchołka grafu w kopcu można przechowywać w dodatkowej tablicy hp zawierającej n elementów typu całkowitego.

Przed rozpoczęciem pracy należy kopiec utworzyć. Ponieważ wszystkie wierzchołki grafu otrzymują początkowo wartość d równą nieskończoności, można je kolejno wpisać do struktury kopca. Następnie wybrany element v w kopcu wymieniamy z elementem pierwszym. Dzięki tej operacji znajdzie się on w korzeniu kopca i zostanie wybrany jako element grafu o najmniejszej wartości kosztu d. Aby efektywnie wykorzystać kopiec w algorytmie Dijkstry znajdowania najkrótszych ścieżek w grafie, w elementach kopca zapamiętujemy numery wierzchołków grafu. Poprzez te numery możemy się prosto odwoływać do tablicy d przechowującej aktualne koszty dojścia do danego wierzchołka w grafie. Również wierzchołki grafu powinny pamiętać swoją pozycję w kopcu. Dzięki temu szybko odnajdziemy wierzchołek, którego koszt d został zmodyfikowany. Pozycję wierzchołka grafu w kopcu można przechowywać w dodatkowej tablicy hp zawierającej n elementów typu całkowitego.

Przed rozpoczęciem pracy należy kopiec utworzyć. Ponieważ wszystkie wierzchołki grafu otrzymują początkowo wartość d równą nieskończoności, można je kolejno wpisać do struktury kopca. Następnie wybrany element v w kopcu wymieniamy z elementem pierwszym. Dzięki tej operacji znajdzie się on w korzeniu kopca i zostanie wybrany jako element grafu o najmniejszej wartości kosztu d.

Używane struktury danych:

n : liczba wierzchołków w grafie.
graf : zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
v : wybrany wierzchołek grafu, v ∈ V, który jest początkiem wyznaczania najkrótszych ścieżek do wszystkich pozostałych wierzchołków.
d[i] : koszt dojścia od wierzchołka v do wierzchołka i-tego wzdłuż najkrótszej ścieżki. Koszt dojścia jest sumą wag krawędzi, przez które przechodzimy posuwając się wzdłuż wyznaczonej najkrótszej ścieżki.
p[i] : dla i-tego wierzchołka grafu p[i] zawiera numer wierzchołka poprzedzającego na najkrótszej ścieżce.
w[i–j] : waga ścieżki pomiędzy wierzchołkami i a j (graf nieskierowany) lub od wierzchołka i-tego do j-tego (graf skierowany).
S : zbiór wierzchołków grafu o policzonych już najkrótszych ścieżkach od wybranego wierzchołka v.
Q : zbiór wierzchołków grafu, dla których najkrótsze ścieżki nie zostały jeszcze policzone.

Dane wejściowe:

n, graf, v.

Dane wyjściowe:

Dla każdego wierzchołka i algorytm wyznacza koszt dojścia d[i] oraz poprzednika p[i] na najkrótszej ścieżce.

Lista kroków:

K01: S ← Ø; Q ← wszystkie wierzchołki grafu
K02: Dla i = 0, 1, …, n - 1:
     wykonuj: p[i] ← -1; d[i] ← ∞
K03: Ustaw kopiec
K04: d[v] ← 0
K05: Odtwórz własność kopca po zmianie d[v]
K06: Dopóki Q ≠ Ø, 
     wykonuj kroki K07…K09
K07:   u ← korzeń kopca
K08:   Usuń korzeń z kopca
       i odtwórz własność kopca
K09:   Wierzchołek u przenieś z Q do S
K10: Dla każdego v ∈ Q, takiego że krawędź u–v ∈ graf:
     wykonuj:
       jeśli d[v] > d[u]+w[u–v],
       to d[v] ← d[u]+w[u–v]; p[v] ← u;
          odtwórz własność kopca po zmianie d[v].
K11: Zakończ

Przy implementacji algorytmu Dijkstry z kolejką priorytetową zastosujemy podobne ustalenia jak dla implementacji z wyszukiwaniem liniowym:

  1. Zbiory S i Q będą odwzorowane w tablicy logicznej QS o n elementach. Element i-ty odnosi się do wierzchołka grafu o numerze i-tym:
    QS[i] = false – wierzchołek i-ty należy do zbioru Q
    QS[i] = true –  wierzchołek i-ty należy do zbioru S
  2. Graf odwzorowujemy w n elementową tablicę list sąsiedztwa.
  3. Koszty dojścia d zrealizujemy w postaci n elementowej tablicy liczb całkowitych. Element d[i] określa koszt dojścia do wierzchołka i-tego.
  4. Poprzedniki p również będą zrealizowane w formie tablicy n elementowej liczb całkowitych. Element p[i] zawiera numer wierzchołka poprzedzającego wierzchołek i-ty na  najkrótszej ścieżce z v do i. Wierzchołki numerujemy poczynając od 0. Zatem zawartość p[i] = -1 informuje nas od razu, iż wierzchołek i-ty nie posiada poprzednika, zatem nie istnieje ścieżka z v do i.
  5. Pętla z kroku 6 będzie zrealizowana w formie zwykłej pętli iteracyjnej wykonywanej n razy. Powodem jest to, iż przy każdym obiegu tej pętli jeden wierzchołek grafu przechodzi zawsze ze zbioru Q do S, zatem zbiór Q stanie się pusty po przeniesieniu n wierzchołków, czyli po wykonaniu n obiegów.
  6. Algorytm wykorzystuje kopiec do wyszukiwania wierzchołków o najmniejszym koszcie dojścia. Kopiec zrealizujemy w n elementowej tablicy h. W kopcu będziemy przechowywali numery wierzchołków grafu. Ponieważ potrzebna nam będzie również informacja o położeniu danego wierzchołka w strukturze kopca (np. przy modyfikacji kosztu w kroku 10), zatem zastosujemy dodatkową n elementową tablicę hp, w której element hp[i] będzie przechowywał położenie i-tego wierzchołka w kopcu. Oczywiście przy modyfikacji kopca również niezbędna będzie odpowiednia modyfikacja tablicy hp, aby zachować spójność danych. Dodatkowo musimy pamiętać aktualną długość kopca w zmiennej hlen.

Operacja z kroku 3: ustaw kopiec

Zadaniem tej operacji jest odpowiednia inicjalizacja struktury kopca. Ponieważ na początku algorytmu Dijkstry dla wszystkich wierzchołków koszt dojścia d[i] przyjmuje wartość nieskończoną (w praktyce największą możliwą), to nie ma istotnego znaczenia, w którym miejscu kopca dany wierzchołek się znajdzie, gdyż własność kopca będzie zachowana. Zatem wierzchołki rozmieszczamy kolejno zgodnie z ich numeracją.

K01: hlen ← n
K02: Dla i = 0, 1, …, n-1:
     wykonuj: h[i] ← i; hp[i] ← i
K03: Koniec

Operacja z kroku 5:odtworzenie własności kopca po zmianie d[v]

Koszt dojścia do elementu startowego v ustalamy zawsze na 0. Operacja ta może zaburzyć strukturę kopca, jeśli v nie jest umieszczony w korzeniu. Ponieważ wszystkie pozostałe wierzchołki na tym etapie posiadają koszty d[i] = ∞, to wystarczy zamienić h[v] z h[0] oraz odpowiednio ustawić tablicę hp.

K01: h[0] ↔ h[v]
K02: hp[v] ← 0; hp[0] ← v
K03: Koniec

Operacja z kroku 7: u ← korzeń kopca

Korzeń kopca zawsze jest w h[0], zatem:

K01: u ← h[0]
K02: Koniec

Operacja z kroku 8: usuń korzeń z kopca i odtwórz własność kopca

Po pobraniu z kopca najmniejszego elementu musimy usunąć korzeń. Posuwamy się w dół hierarchii kopca:

Używane struktury danych:

hlen : ilość elementów w kopcu.
parent : indeks wierzchołka nadrzędnego.
left : indeks lewego potomka.
right : indeks prawego potomka.
dmin : mniejsza wartość kosztu dojścia do lewego lub prawego potomka.
pmin : indeks potomka zawierającego mniejszą wartość kosztu dojścia.

Lista kroków:

K01: h[0] ← h[hlen-1]; hlen ← hlen-1
K02: hp[h0]] ← 0
K03: parent ← 0
K04: left ← 2 x parent = 1;  right ← left+1
K05: Jeśli left ≥ hlen, 
     to zakończ
K06: dmin ← d[h[left]]; pmin ← left
K07: Jeśli right ≥ hlenn, 
     to idź do kroku K09
K08: Jeśli dmin > d[h[right]], 
     to dmin ← d[h[right]]; pmin ← right
K09: Jeśli d[h[parent]] ≤ dmin, 
     to zakończ
K10: h[parent] ↔ h[pmin]
K11: hp[h[parent]] ← parent; hp[h[pmin]] ← pmin
K12: parent ← pmin
K13: Idź do kroku K04

Operacja z kroku 10: odtwórz własność kopca po zmianie d(v)

Algorytm zmodyfikował koszt dojścia do wierzchołka v połączonego krawędzią ze znalezionym wcześniej wierzchołkiem u grafu. W takim przypadku własność kopca zostaje zaburzona w okolicy wierzchołka v w kopcu. Musimy ją przywrócić. Posuwamy się w górę hierarchii kopca:

Używane struktury danych:

parent : indeks elementu nadrzędnego w hierarchii kopca,
child : indeks elementu potomnego.

Lista kroków:

K01: child ← hp[v]
K02: Jeśli child = 0, 
     to zakończ
K03: parent ← [(child - 1) / 2]
K04: Jeśli d[h[parent]] ≤ d[h[child]], 
     to zakończ
K05: h[parent] ↔ h[child]
K06: hp[h[parent]] ← parent; hp[h[child]] ← child
K07: child ← parent
K08: Idź do kroku K02

Podstawowym zyskiem zastosowania kolejki priorytetowej w algorytmie Dijkstry jest zmniejszenie klasy złożoności obliczeniowej z O(n2) na O(n log n). Jednakże z drugiej strony sam algorytm się komplikuje i rośnie zapotrzebowanie na pamięć. Dlatego dla małych grafów wciąż efektywnym rozwiązaniem może być wersja z wyszukiwaniem liniowym.

Często interesuje nas znalezienie najkrótszej ścieżki pomiędzy wybranymi wierzchołkami w grafie – reszta ścieżek jest nam niepotrzebna. W takim przypadku przedstawiony algorytm Dijkstry kończymy w kroku, w którym pobieramy wierzchołek u o najmniejszym koszcie ze zbioru Q i jest on wierzchołkiem końcowym szukanej ścieżki. Pozwala to efektywnie konstruować algorytmy znajdujące np. najlepsze trasy przechodzące poprzez zadane wierzchołki w grafie.

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.
Poniższy program jest przykładową realizacją algorytmu Dijkstry z kolejką priorytetową opartą na kopcu binarnym. Definicja danych wejściowych jest następująca:

W pierwszym wierszu program odczytuje kolejno numer wierzchołka startowego v, liczbę wierzchołków n oraz liczbę krawędzi m. W m kolejnych wierszach znajdują się definicje krawędzi. Definicja składa się z trzech liczb x y w. Pierwsza i druga liczba określa wierzchołki grafu, które są ze sobą połączone tą krawędzią – krawędź biegnie od wierzchołka x do wierzchołka y. Trzecia liczba jest wagą w krawędzi.

Na wyjściu program wypisuje znalezione najkrótsze ścieżki od wierzchołka v do wszystkich pozostałych wierzchołków. Oprócz ścieżki wypisywany jest również koszt przejścia tej ścieżki.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):
obrazek 0 6 9
0 1 3
0 4 3
1 2 1
2 3 3
2 5 1
3 1 3
4 5 2
5 0 6
5 3 1
Pascal
// Algorytm Dijkstry
// z kolejką priorytetową
// Data: 16.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program dijkstra;

// Typy danych
type
  PSLel = ^SLel;
  SLel =  record
    next : PSLel;
    // numer węzła docelowego
    // i waga krawędzi
    v, w : integer;
  end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  i,j,m,n,v,u,w,x,y : integer;
  sptr, hlen, parent : integer;
  left, right : integer;
  dmin, pmin, child : integer;
  d,p,S,h,hp : array of integer;
  // Zbiory Q i S
  QS : array of boolean;
  // Tablica list sąsiedztwa
  graf : array of PSLel;
  pw, rw : PSLel;

begin
  // Węzeł startowy,
  // liczba wierzchołków
  // i krawędzi
  read(v, n, m);
  // Tworzymy
  // tablice dynamiczne
  //-------------------
  // Tablica kosztów dojścia
  SetLength(d, n);
  // Tablica poprzedników
  SetLength(p, n);
  // Zbiory Q i S
  SetLength(QS, n);
  // Tablica list sąsiedztwa
  SetLength(graf, n);
  // Stos
  SetLength(S, n);
  // Kopiec
  SetLength(h, n);
  // Pozycje w kopcu
  SetLength(hp, n);
  // Wskaźnik stosu
  sptr := 0;
  // Inicjujemy
  // tablice dynamiczne
  for i := 0 to n-1 do
  begin
    d[i] := MAXINT;
    p[i] := -1;
    QS[i] := false;
    graf[i] := nil;
    h[i] := i;
    hp[i] := i;
  end;
  hlen := n;
  // Odczytujemy
  // dane wejściowe
  for i := 1 to m do
  begin
    // Odczytujemy
    // krawędź z wagą
    read(x, y, w);
    // Tworzymy element
    // listy sąsiedztwa
    new(pw);
    // Wierzchołek
    // docelowy krawędzi
    pw^.v := y;
    // Waga krawędzi
    pw^.w := w;
    pw^.next := graf[x];
    // Element
    // dołączamy do listy
    graf[x] := pw;
  end;
  writeln;
  // Koszt dojścia v
  // jest zerowy
  d[v] := 0;
  // Odtwarzamy
  // własność kopca
  x := h[0];
  h[0] := h[v];
  h[v] := x;
  hp[v] := 0;
  hp[0] := v;
  // Wyznaczamy ścieżki
  for i := 1 to n do
  begin
    // Korzeń kopca jest
    // zawsze najmniejszy
    u := h[0];
    // Usuwamy korzeń z kopca,
    // odtwarzając własność kopca
    //---------------------------
    // W korzeniu umieszczamy
    // ostatni element
    h[0] := h[hlen-1];
    // Kopiec jest krótszy
    // o jeden element
    dec(hlen);
    // Zapamiętujemy pozycję
    // elementu w kopcu
    hp[h[0]] := 0;
    parent := 0;
    // W pętli idziemy w dół kopca,
    // przywracając go
    while true do
    begin
      // Pozycja lewego potomka
      left := parent+parent+1;
      // Pozycja prawego potomka
      right := left+1;
      // Kończymy,
      // jeśli lewy potomek
      // poza kopcem
      if left >= hlen then break;
      // Wyznaczamy
      // mniejszego potomka
      dmin := d[h[left]];
      pmin := left;
      if (right < hlen) and
         (dmin > d[h[right]]) then
      begin
        dmin := d[h[right]];
        pmin := right;
      end;
      // Jeśli własność
      // kopca zachowana,
      // kończymy
      if d[h[parent]] <= dmin then
        break;
      // Przywracamy
      // własność kopca
      x := h[parent];
      h[parent] := h[pmin];
      h[pmin] := x;
      // na danym poziomie
      hp[h[parent]] := parent;
      hp[h[pmin]] := pmin;
      // i przechodzimy
      // na niższy poziom kopca
      parent := pmin;
    end;
    // Znaleziony wierzchołek
    // przenosimy do S
    QS[u] := true;
    // Modyfikujemy wszystkich
    // sąsiadów u, którzy są w Q
    pw := graf[u];
    while pw <> nil do
    begin
      if not QS[pw^.v] and
         (d[pw^.v] >
          d[u]+pw^.w) then
      begin
        d[pw^.v] := d[u]+pw^.w;
        p[pw^.v] := u;
        // Po zmianie d[v]
        // odtwarzamy własność
        // kopca, idąc w górę
        child := hp[pw^.v];
        while child > 0 do
        begin
          parent := child div 2;
          if d[h[parent]] <=
             d[h[child]] then
            break;
          x := h[parent];
          h[parent] := h[child];
          h[child] := x;
          hp[h[parent]] := parent;
          hp[h[child]] := child;
          child := parent;
        end;
      end;
      pw := pw^.next;
    end;
  end;
  // Gotowe,
  // wyświetlamy wyniki
  for i := 0 to n-1 do
  begin
    write(i, ': ');
    // Ścieżkę przechodzimy
    // od końca ku początkowi,
    // zapisując na stosie
    // kolejne wierzchołki
    j := i;
    while j > -1 do
    begin
      S[sptr] := j;
      inc(sptr);
      j := p[j];
    end;
    // Wyświetlamy ścieżkę,
    // pobierając wierzchołki
    // ze stosu
    while sptr > 0 do
    begin
      dec(sptr);
      write(S[sptr], ' ');
    end;
    // Na końcu ścieżki
    // wypisujemy jej koszt
    writeln('$', d[i]);
  end;
  // Usuwamy
  // tablice dynamiczne
  SetLength(d, 0);
  SetLength(p, 0);
  SetLength(QS, 0);
  SetLength(S, 0);
  SetLength(h, 0);
  SetLength(hp, 0);
  for i := 0 to n-1 do
  begin
    pw := graf[i];
    while pw <> nil do
    begin
      rw := pw;
      pw := pw^.next;
      dispose(rw);
    end;
  end;
  SetLength(graf, 0);
end.
C++
// Algorytm Dijkstry
// z kolejką priorytetową
// Data: 16.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// Typy danych
struct SLel
{
  SLel * next;
  // numer węzła docelowego
  // i waga krawędzi
  int v, w;
};

const int MAXINT = 2147483647;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int i,j,m,n,v,u,w,x,y;
  int sptr,hlen,parent,left,right;
  int dmin,pmin,child;
  int *d, *p, *S, *h, *hp;
  // Zbiory Q i S
  bool *QS;
  // Tablica list sąsiedztwa
  SLel **graf;
  SLel *pw, *rw;
  // Tablica list sąsiedztwa
  cin >> v >> n >> m;
  // Tworzymy tablice dynamiczne
  //----------------------------
  // Tablica kosztów dojścia
  d = new int [n];
  // Tablica poprzedników
  p = new int [n];
  // Zbiory Q i S
  QS = new bool [n];
  // Tablica list sąsiedztwa
  graf = new SLel * [n];
  // Stos
  S = new int [n];
  // Kopiec
  h = new int [n];
  // Pozycje w kopcu
  hp = new int [n];
  // Wskaźnik stosu
  sptr = 0;
  // Inicjujemy
  // tablice dynamiczne
  for(i = 0; i < n; i++)
  {
    d[i] = MAXINT;
    p[i] = -1;
    QS[i] = false;
    graf[i] = nullptr;
    h[i] = hp[i] = i;
  }
  hlen = n;
  // Odczytujemy
  // dane wejściowe
  for(i = 0; i < m; i++)
  {
    // Odczytujemy
    // krawędź z wagą
    cin >> x >> y >> w;
    // Tworzymy element
    // listy sąsiedztwa
    pw = new SLel;
    // Wierzchołek
    // docelowy krawędzi
    pw->v = y;
    // Waga krawędzi
    pw->w = w;
    pw->next = graf[x];
    // Element
    // dołączamy do listy
    graf[x] = pw;
  }
  cout << endl;
  // Koszt dojścia v
  // jest zerowy
  d[v] = 0;
  // odtwarzamy
  // własność kopca
  x = h[0];
  h[0] = h[v];
  h[v] = x;
  hp[v] = 0;
  hp[0] = v;
  // Wyznaczamy ścieżki
  for(i = 0; i < n; i++)
  {
    // Korzeń kopca jest
    // zawsze najmniejszy
    u = h[0];
    // Usuwamy korzeń z kopca,
    // odtwarzając własność kopca
    //---------------------------
    // W korzeniu umieszczamy
    // ostatni element
    h[0] = h[--hlen];
    // Zapamiętujemy pozycję
    // elementu w kopcu
    hp[h[0]] = parent = 0;
    // W pętli idziemy
    // w dół kopca,
    // przywracając go
    while(true)
    {
      // Pozycja lewego potomka
      left = parent+parent+1;
      // Pozycja prawego potomka
      right = left+1;
      // Kończymy, jeśli
      // lewy potomek poza kopcem
      if(left >= hlen) break;
      // Wyznaczamy
      // mniejszego potomka
      dmin = d[h[left]];
      pmin = left;
      if((right < hlen) &&
         (dmin > d[h[right]]))
      {
        dmin = d[h[right]];
        pmin = right;
      }
      // Jeśli własność kopca
      // zachowana, kończymy
      if(d[h[parent]] <= dmin)
        break;
      // Przywracamy
      // własność kopca
      x = h[parent];
      h[parent] = h[pmin];
      h[pmin] = x;
      hp[h[parent]] = parent;
      // na danym poziomie
      hp[h[pmin]] = pmin;
      // i przechodzimy
      // na niższy poziom kopca
      parent = pmin;
    }
    // Znaleziony wierzchołek
    // przenosimy do S
    QS[u] = true;
    // Modyfikujemy odpowiednio
    // wszystkich sąsiadów u,
    // którzy są w Q
    for(pw = graf[u]; pw;
        pw = pw->next)
      if(!QS[pw->v] &&
         (d[pw->v] > d[u]+pw->w))
      {
        d[pw->v] = d[u]+pw->w;
        p[pw->v] = u;
        // Po zmianie d[v]
        // odtwarzamy własność
        // kopca, idąc w górę
        for(child = hp[pw->v];
            child; child = parent)
        {
          parent = child / 2;
          if(d[h[parent]] <=
             d[h[child]]) break;
          x = h[parent];
          h[parent] = h[child];
          h[child] = x;
          hp[h[parent]] = parent;
          hp[h[child]] = child;
        }
      }
  }
  // Gotowe, wyświetlamy wyniki
  for(i = 0; i < n; i++)
  {
    cout << i << ": ";
    // Ścieżkę przechodzimy
    // od końca ku początkowi,
    // zapisując na stosie
    // kolejne wierzchołki
    for(j = i; j > -1; j = p[j])
      S[sptr++] = j;
    // Wyświetlamy ścieżkę,
    // pobierając wierzchołki
    // ze stosu
    while(sptr)
      cout << S[--sptr] << " ";
    // Na końcu ścieżki
    // wypisujemy jej koszt
    cout << "$" << d [i] << endl;
  }
  // Usuwamy tablice dynamiczne
  delete [] d;
  delete [] p;
  delete [] QS;
  delete [] S;
  delete [] h;
  delete [] hp;
  for(i = 0; i < n; i++)
  {
    pw = graf[i];
    while(pw)
    {
      rw = pw;
      pw = pw->next;
      delete rw;
    }
  }
  delete [] graf;
  return 0;
}
Basic
' Algorytm Dijkstry
' z kolejką priorytetową
' Data: 16.03.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Typy danych
Type SLel
  Dim As SLel Ptr Next
  ' numer węzła docelowego
  ' i waga krawędzi
  Dim As Integer v, w
End Type

const MAXINT = 2147483647

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer i,j,m,n,v,u,w,x,y
Dim As Integer sptr,hlen,parent
Dim As Integer leftc,rightc
Dim As Integer dmin,pmin,child
Dim As Integer Ptr d,p,S,h,hp
' Zbiory Q i S
Dim As Byte Ptr QS
' Tablica list sąsiedztwa
Dim As SLel Ptr Ptr graf
Dim As SLel Ptr pw, rw

Open Cons For Input As #1
' Węzeł startowy,
' liczba wierzchołków
' i krawędzi
Input #1, v, n, m
' Tworzymy
' tablice dynamiczne
'-------------------
' Tablica
' kosztów dojścia
d = New integer [n]
' Tablica poprzedników
p = New integer [n]
' Zbiory Q i S
QS = New Byte [n]
' Tablica
' list sąsiedztwa
graf = New SLel Ptr [n]
' Stos
S = New Integer [n]
' Kopiec
h = New Integer [n]
' Pozycje w kopcu
hp = New Integer [n]
' Wskaźnik stosu
sptr = 0
' Inicjujemy
' tablice dynamiczne
For i = 0 To n-1
  d[i] = MAXINT
  p[i] = -1
  QS[i] = 0
  graf[i] = 0
  h[i] = i
  hp[i] = i
Next
hlen = n
' Odczytujemy
' dane wejściowe
For i = 0 To m-1
  ' Odczytujemy
  ' krawędź z wagą
  Input #1, x, y, w
  ' Tworzymy element
  ' listy sąsiedztwa
  pw = New SLel
  ' Wierzchołek
  ' docelowy krawędzi
  pw->v = y
  ' Waga krawędzi
  pw->w = w
  ' Element dołączamy
  ' do listy
  pw->next = graf[x]
  graf[x] = pw
Next
Close #1
Print
' Koszt dojścia v
' jest zerowy
d[v] = 0
' Odtwarzamy
' własność kopca
Swap h[0],h[v]
hp[v] = 0
hp[0] = v
' Wyznaczamy ścieżki
For i = 0 To n-1
  ' Korzeń kopca jest
  ' zawsze najmniejszy
  u = h[0]
  ' Usuwamy korzeń z kopca,
  ' odtwarzając własność kopca
  hlen -= 1
  ' W korzeniu umieszczamy
  ' ostatni element
  h[0] = h[hlen]
  ' Zapamiętujemy pozycję
  ' elementu w kopcu
  hp[h[0]] = 0
  parent = 0
  ' W pętli idziemy w dół kopca,
  ' przywracając go
  While 1
    ' Pozycja lewego potomka
    leftc  = parent+parent+1
    ' Pozycja prawego potomka
    rightc = leftc+1
    If leftc >= hlen Then
      ' Kończymy, jeśli
      ' lewy potomek poza kopcem
      Exit While
    End If
    ' Wyznaczamy
    ' mniejszego potomka
    dmin = d[h[leftc]]
    pmin = leftc
    if (rightc < hlen) AndAlso _
       (dmin > d[h[rightc]]) Then
      dmin = d[h[rightc]]
      pmin = rightc
    End If
    If d[h[parent]] <= dmin Then
      ' Jeśli własność kopca
      ' zachowana, kończymy
      Exit While
    End If
    ' Przywracamy własność kopca
    Swap h[parent], h[pmin]
    ' na danym poziomie
    hp[h[parent]] = parent
    hp[h[pmin]] = pmin
    ' i przechodzimy
    ' na niższy poziom kopca
    parent = pmin
  Wend
 ' Znaleziony wierzchołek
 ' przenosimy do S
  QS[u] = 1
  ' Modyfikujemy odpowiednio
  ' wszystkich sąsiadów u,
  ' którzy są w Q
  pw = graf[u]
  While pw <> 0
    If (QS[pw->v] = 0) AndAlso _
       (d[pw->v] > d[u]+pw->w) Then
      d[pw->v] = d[u]+pw->w
      p[pw->v] = u
      ' Po zmianie d[v]
      ' odtwarzamy własność kopca,
      ' idąc w górę
      child = hp[pw->v]
      While child > 0
        parent = child \ 2
        If d[h[parent]] <= _
           d[h[child]] Then Exit While
        Swap h[parent], h[child]
        hp[h[parent]] = parent
        hp[h[child]] = child
        child = parent
      Wend
    End If
    pw = pw->Next
  Wend
Next
' Gotowe, wyświetlamy wyniki
For i = 0 To n-1
  Print i;":";
  ' Ścieżkę przechodzimy
  ' od końca ku początkowi, 
  ' zapisując na stosie
  ' kolejne wierzchołki
  j = i
  While j > -1
    S[sptr] = j
    sptr += 1
    j = p[j]
  Wend
  ' Wyświetlamy ścieżkę,
  ' pobierając wierzchołki
  ' ze stosu
  While sptr > 0
    sptr -= 1
    Print S[sptr];
  Wend
  ' Na końcu ścieżki
  ' wypisujemy jej koszt
  Print Using " $&";d[i]
Next
' Usuwamy tablice dynamiczne
Delete [] d
Delete [] p
Delete [] QS
Delete [] S
Delete [] h
Delete [] hp
For i = 0 To n-1
  pw = graf[i]
  While pw
    rw = pw
    pw = pw->Next
    Delete rw
  Wend
Next
Delete [] graf
End
Python (dodatek)
# Algorytm Dijkstry
# z kolejką priorytetową
# Data: 16.02.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Klasa listy
class SLel:
    def __init__(self):
        self.next = None
        # numer węzła docelowego
        # i waga krawędzi
        self.v = 0
        self.w = 0


MAXINT = 2147483647

# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Węzeł startowy,
# liczba wierzchołków
# i krawędzi
z = input().split()
v = int(z[0])
n = int(z[1])
m = int(z[2])
# Tworzymy
# tablice dynamiczne
#-------------------
# Tablica
# kosztów dojścia
d = [MAXINT] * n
# Tablica poprzedników
p = [-1] * n
# Zbiory Q i S
qs = [False] * n
# Tablica
# list sąsiedztwa
graf = [None] * n
# Stos
s = [0] * n
# Kopiec
h = [0] * n
# Pozycje w kopcu
hp = [0] * n
# Wskaźnik stosu
sptr = 0
# Inicjujemy
# tablice dynamiczne
for i in range(n):
    h[i] = i
    hp[i] = i
hlen = n
# Odczytujemy
# dane wejściowe
for i in range(m):
    # Odczytujemy
    # krawędź z wagą
    z = input().split()
    x = int(z[0])
    y = int(z[1])
    w = int(z[2])
    # Tworzymy element
    # listy sąsiedztwa
    pw = SLel()
    # Wierzchołek
    # docelowy krawędzi
    pw.v = y
    # Waga krawędzi
    pw.w = w
    # Element dołączamy
    # do listy
    pw.next = graf[x]
    graf[x] = pw
print()
# Koszt dojścia v
# jest zerowy
d[v] = 0
# Odtwarzamy
# własność kopca
h[0],h[v] = h[v],h[0]
hp[v] = 0
hp[0] = v
# Wyznaczamy ścieżki
for i in range(n):
    # Korzeń kopca jest
    # zawsze najmniejszy
    u = h[0]
    # Usuwamy korzeń z kopca,
    # odtwarzając własność kopca
    hlen -= 1
    # W korzeniu umieszczamy
    # ostatni element
    h[0] = h[hlen]
    # Zapamiętujemy pozycję
    # elementu w kopcu
    hp[h[0]] = 0
    parent = 0
    # W pętli idziemy w dół kopca,
    # przywracając go
    while True:
        # Pozycja lewego potomka
        leftc = parent+parent+1
        # Pozycja prawego potomka
        rightc = leftc+1
        if leftc >= hlen:
            # Kończymy, jeśli
            # lewy potomek poza kopcem
            break
        # Wyznaczamy
        # mniejszego potomka
        dmin = d[h[leftc]]
        pmin = leftc
        if (rightc < hlen) and \
           (dmin > d[h[rightc]]):
            dmin = d[h[rightc]]
            pmin = rightc
        if d[h[parent]] <= dmin:
            # Jeśli własność kopca
            # zachowana, kończymy
            break
        # Przywracamy własność kopca
        h[parent], h[pmin] = \
        h[pmin], h[parent]
        # na danym poziomie
        hp[h[parent]] = parent
        hp[h[pmin]] = pmin
        # i przechodzimy
        # na niższy poziom kopca
        parent = pmin
    # Znaleziony wierzchołek
    # przenosimy do S
    qs[u] = 1
    # Modyfikujemy odpowiednio
    # wszystkich sąsiadów u,
    # którzy są w Q
    pw = graf[u]
    while pw:
        if not qs[pw.v] and \
           (d[pw.v] > d[u]+pw.w):
            d[pw.v] = d[u]+pw.w
            p[pw.v] = u
            # Po zmianie d[v]
            # odtwarzamy własność kopca,
            # idąc w górę
            child = hp[pw.v]
            while child:
                parent = child // 2
                if d[h[parent]] <= \
                   d[h[child]]:
                    break
                h[parent], h[child] = \
                h[child], h[parent]
                hp[h[parent]] = parent
                hp[h[child]] = child
                child = parent
        pw = pw.next
# Gotowe, wyświetlamy wyniki
for i in range(n):
    print(i,": ",sep="",end="")
    # Ścieżkę przechodzimy
    # od końca ku początkowi, 
    # zapisując na stosie
    # kolejne wierzchołki
    j = i
    while j > -1:
        s[sptr] = j
        sptr += 1
        j = p[j]
    # Wyświetlamy ścieżkę,
    # pobierając wierzchołki
    # ze stosu
    while sptr:
        sptr -= 1
        print(s[sptr],end=" ")
    # Na końcu ścieżki
    # wypisujemy jej koszt
    print(" $",d[i],sep="")
# Usuwamy tablice dynamiczne
del d,p,qs,s,h,hp
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
del graf
Wynik:
0 6 9
0 1 3
0 4 3
1 2 1
2 3 3
2 5 1
3 1 3
4 5 2
5 0 6
5 3 1

0: 0 $0
1: 0 1 $3
2: 0 1 2 $4
3: 0 4 5 3 $6
4: 0 4 $3
5: 0 4 5 $5

do podrozdziału  do strony 
Zespół Przedmiotowy
Chemii-Fizyki-Informatyki
w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2026 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.