Algorytmy i Struktury Danych - Algorytm Dijkstry

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).

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.

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:

Wybieramy ze zbioru Q wierzchołek u o najmniejszym koszcie dojścia d (u).
Wybrany wierzchołek u usuwamy ze zbioru Q i dodajemy do zbioru S.
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:

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.

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.

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.

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.

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.

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.

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

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.

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:

Dojście do wierzchołka 0: ścieżka pusta, koszt 0
Dojście do wierzchołka 1: 0 – 1, koszt 3
Dojście do wierzchołka 2: 0 – 1 – 2, koszt 4
Dojście do wierzchołka 3: 0 – 4 – 5 – 3, koszt 6
Dojście do wierzchołka 4: 0 – 4, koszt 3
Dojście do wierzchołka 5: 0 – 4 – 5, koszt 5

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 ustawiamy 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 : wykonuj kroki K11…K12	przeglądamy sąsiadów przeniesionego wierzchołka
K11:	Jeśli w nie jest w Q, to następny obieg pętli K10	szukamy sąsiadów obecnych w Q
K12:	Jeśli d [w] > d [u ]+waga krawędzi u – w, to: d [w] ← d [u]+waga krawędzi u – w p [w] ← u	sprawdzamy koszt dojścia. Jeśli mamy niższy, 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 ( n²). 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):

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;
    v, w   : integer;        // numer węzła docelowego i waga krawędzi
  end;

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

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

begin
  read (v, n, m);          // Węzeł startowy, liczba wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  SetLength (d, n);    // Tablica kosztów dojścia
  SetLength (p, n);    // Tablica poprzedników
  SetLength (QS, n);   // Zbiory Q i S
  SetLength (graf, n); // Tablica list sąsiedztwa
  SetLength (S, n);    // Stos
  sptr := 0;             // Wskaźnik stosu

  // 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
    read (x, y, w);       // Odczytujemy krawędź z wagą
    new (pw);             // Tworzymy element listy sąsiedztwa
    pw^.v := y;             // Wierzchołek docelowy krawędzi
    pw^.w := w;             // Waga krawędzi
    pw^.next := graf [x];
    graf [x] := pw;       // Element dołączamy do listy
  end;

  writeln;

  d [v] := 0;             // Koszt dojścia v jest zerowy

  // 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;
  int v, w;           // numer węzła docelowego i waga krawędzi
};

const int MAXINT = 2147483647;

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

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

  cin >> v >> n >> m; // Węzeł startowy, liczba wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  d = new int [n];          // Tablica kosztów dojścia
  p = new int [n];          // Tablica poprzedników
  QS = new bool [n];        // Zbiory Q i S
  graf = new SLel * [n]; // Tablica list sąsiedztwa
  S = new int [n];          // Stos
  sptr = 0;                   // Wskaźnik stosu

  // Inicjujemy tablice dynamiczne

  for(i = 0; i < n; i++)
  {
    d [i] = MAXINT;
    p [i] = -1;
    QS [i] = false;
    graf [i] = NULL;
  }

  // Odczytujemy dane wejściowe

  for(i = 0; i < m; i++)
  {
    cin >> x >> y >> w;    // Odczytujemy krawędź z wagą
    pw = new SLel;      // Tworzymy element listy sąsiedztwa
    pw->v = y;             // Wierzchołek docelowy krawędzi
    pw->w = w;             // Waga krawędzi
    pw->next = graf [x];
    graf [x] = pw;       // Element dołączamy do listy
  }

  cout << endl;

  d [v] = 0;             // Koszt dojścia v jest zerowy

  // 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
  Dim As Integer v, w        ' numer węzła docelowego i waga krawędzi
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
Dim As Byte Ptr QS           ' Zbiory Q i S
Dim As SLel Ptr Ptr graf  ' Tablica list sąsiedztwa
Dim As SLel Ptr pw, rw

Open Cons For Input As #1

Input #1, v, n, m            ' Węzeł startowy, liczba wierzchołków i krawędzi

' Tworzymy tablice dynamiczne

d = New integer [n]        ' Tablica kosztów dojścia
p = New integer [n]        ' Tablica poprzedników
QS = New Byte [n]          ' Zbiory Q i S
graf = New SLel Ptr [n] ' Tablica list sąsiedztwa
S = New Integer [n]        ' Stos
sptr = 0                     ' Wskaźnik stosu

' 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
  Input #1, x, y, w     ' Odczytujemy krawędź z wagą
  pw = New SLel      ' Tworzymy element listy sąsiedztwa
  pw->v = y             ' Wierzchołek docelowy krawędzi
  pw->w = w             ' Waga krawędzi
  pw->next = graf [x]
  graf [x] = pw       ' Element dołączamy do listy
Next

Close #1

Print

d [v] = 0             ' Koszt dojścia v jest zerowy

' 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
    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

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.

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.

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 K05…K07
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:

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
Graf odwzorowujemy w n-elementową tablicę list sąsiedztwa.
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.
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.
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.
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 h_len.

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:	h_len ← 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] = nieskończoność, 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:

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

Lista kroków:

K01:	h [0] ← h [h_len-1]; h_len ← h_len-1
K02:	hp [h [0]] ← 0
K03:	parent ← 0
K04:	left ← 2 x parent = 1; right ← left+1
K05:	Jeśli left ≥ h_len, to zakończ
K06:	d_min ← d [h [left]]; p_min ← left
K07:	Jeśli right ≥ h_len, to idź do kroku K09
K08:	Jeśli d_min > d [h [right]], to d_min ← d [h [right]]; p_min ← right
K09:	Jeśli d [h [parent]] ≤ d_min, to zakończ
K10:	h [parent] ↔ h [p_min]
K11:	hp [h [parent]] ← parent; hp [h [p_min]] ← p_min
K12:	parent ← p_min
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 ( n²) 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ą 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):

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;
    v, w   : integer;        // numer węzła docelowego i waga krawędzi
  end;

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

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

begin
  read (v, n, m);          // Węzeł startowy, liczba wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  SetLength (d, n);    // Tablica kosztów dojścia
  SetLength (p, n);    // Tablica poprzedników
  SetLength (QS, n);   // Zbiory Q i S
  SetLength (graf, n); // Tablica list sąsiedztwa
  SetLength (S, n);    // Stos
  SetLength (h, n);    // Kopiec
  SetLength (hp, n);   // Pozycje w kopcu
  sptr := 0;             // Wskaźnik stosu

  // 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
    read (x, y, w);             // Odczytujemy krawędź z wagą
    new (pw);                   // Tworzymy element listy sąsiedztwa
    pw^.v := y;                   // Wierzchołek docelowy krawędzi
    pw^.w := w;                   // Waga krawędzi
    pw^.next := graf [x];
    graf [x] := pw;             // Element dołączamy do listy
  end;

  writeln;

  d [v] := 0;                   // Koszt dojścia v jest zerowy
  x := h [0]; h [0] := h [v]; h [v] := x; // odtwarzamy własność kopca
  hp [v] := 0; hp [0] := v;

  // Wyznaczamy ścieżki

  for i := 1 to n do
  begin

    u := h [0];                 // Korzeń kopca jest zawsze najmniejszy

    // Usuwamy korzeń z kopca, odtwarzając własność kopca

    h [0] := h [hlen-1];    // W korzeniu umieszczamy ostatni element
    dec (hlen);                 // Kopiec jest krótszy o jeden element
    hp [h [0]] := 0;          // Zapamiętujemy pozycję elementu w kopcu
    parent   := 0;
    while true do                 // W pętli idziemy w dół kopca, przywracając go
    begin
      left  := parent+parent+1; // Pozycja lewego potomka
      right := left+1;          // Pozycja prawego potomka
      if left >= hlen then break; // Kończymy, jeśli lewy potomek poza kopcem
      dmin := d [h [left]];   // Wyznaczamy mniejszego potomka
      pmin := left;
      if(right < hlen) and (dmin > d [h [right]]) then
      begin
        dmin := d [h [right]];
        pmin := right;
      end;
      if d [h [parent]] <= dmin then break; // Jeśli własność kopca zachowana, kończymy
      x := h [parent]; h [parent] := h [pmin]; h [pmin] := x; // Przywracamy własność kopca
      hp [h [parent]] := parent; hp [h [pmin]] := pmin;       // na danym poziomie
      parent := pmin;             // i przechodzimy na poziom niższy kopca
    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;
  int v, w;                   // numer węzła docelowego i waga krawędzi
};

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, dmin, pmin, child;
  int *d, *p, *S, *h, *hp;
  bool *QS;                   // Zbiory Q i S
  SLel **graf;             // Tablica list sąsiedztwa
  SLel *pw, *rw;

  cin >> v >> n >> m;         // Węzeł startowy, liczba wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  d    = new int [n];       // Tablica kosztów dojścia
  p    = new int [n];       // Tablica poprzedników
  QS   = new bool [n];      // Zbiory Q i S
  graf = new SLel * [n]; // Tablica list sąsiedztwa
  S    = new int [n];       // Stos
  h    = new int [n];       // Kopiec
  hp   = new int [n];       // Pozycje w kopcu
  sptr = 0;                   // Wskaźnik stosu

  // Inicjujemy tablice dynamiczne

  for(i = 0; i < n; i++)
  {
    d [i] = MAXINT;
    p [i] = -1;
    QS [i] = false;
    graf [i] = NULL;
    h [i] = hp [i] = i;
  }

  hlen = n;

  // Odczytujemy dane wejściowe

  for(i = 0; i < m; i++)
  {
    cin >> x >> y >> w;           // Odczytujemy krawędź z wagą
    pw = new SLel;             // Tworzymy element listy sąsiedztwa
    pw->v = y;                    // Wierzchołek docelowy krawędzi
    pw->w = w;                    // Waga krawędzi
    pw->next = graf [x];
    graf [x] = pw;              // Element dołączamy do listy
  }

  cout << endl;

  d [v] = 0;                    // Koszt dojścia v jest zerowy
  x = h [0]; h [0] = h [v]; h [v] = x; // odtwarzamy własność kopca
  hp [v] = 0; hp [0] = v;

  // Wyznaczamy ścieżki

  for(i = 0; i < n; i++)
  {
    u = h [0];                  // Korzeń kopca jest zawsze najmniejszy

    // Usuwamy korzeń z kopca, odtwarzając własność kopca

    h [0] = h [--hlen];       // W korzeniu umieszczamy ostatni element
    hp [h [0]] = parent = 0;  // Zapamiętujemy pozycję elementu w kopcu
    while(true)                 // W pętli idziemy w dół kopca, przywracając go
    {
      left  = parent+parent+1; // Pozycja lewego potomka
      right = left+1;           // Pozycja prawego potomka
      if(left >= hlen) break;   // Kończymy, jeśli lewy potomek poza kopcem
      dmin = d [h [left]];    // Wyznaczamy mniejszego potomka
      pmin = left;
      if((right < hlen) && (dmin > d [h [right]]))
      {
        dmin = d [h [right]];
        pmin = right;
      }
      if(d [h [parent]] <= dmin) break; // Jeśli własność kopca zachowana, kończymy
      x = h [parent]; h [parent] = h [pmin]; h [pmin] = x; // Przywracamy własność kopca
      hp [h [parent]] = parent; hp [h [pmin]] = pmin;      // na danym poziomie
      parent = pmin;              // i przechodzimy na poziom niższy kopca
    }

    // 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
  Dim As Integer v, w            ' numer węzła docelowego i waga krawędzi
End Type

const MAXINT = 2147483647

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

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

Open Cons For Input As #1

Input #1, v, n, m                ' Węzeł startowy, liczba wierzchołków i krawędzi

' Tworzymy tablice dynamiczne

d    = New integer [n]         ' Tablica kosztów dojścia
p    = New integer [n]         ' Tablica poprzedników
QS   = New Byte [n]            ' Zbiory Q i S
graf = New SLel Ptr [n]     ' Tablica list sąsiedztwa
S    = New Integer [n]         ' Stos
h    = New Integer [n]         ' Kopiec
hp   = New Integer [n]         ' Pozycje w kopcu
sptr = 0                         ' Wskaźnik stosu

' 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
  Input #1, x, y, w               ' Odczytujemy krawędź z wagą
  pw = New SLel                ' Tworzymy element listy sąsiedztwa
  pw->v = y                       ' Wierzchołek docelowy krawędzi
  pw->w = w                       ' Waga krawędzi
  pw->next = graf [x]
  graf [x] = pw                 ' Element dołączamy do listy
Next

Close #1

Print

d [v] = 0                       ' Koszt dojścia v jest zerowy
Swap h [0], h [v]             ' odtwarzamy własność kopca
hp [v] = 0: hp [0] = v

' Wyznaczamy ścieżki

For i = 0 To n-1

  u = h [0]                     ' Korzeń kopca jest zawsze najmniejszy

  ' Usuwamy korzeń z kopca, odtwarzając własność kopca

  hlen -= 1
  h [0] = h [hlen]            ' W korzeniu umieszczamy ostatni element
  hp [h [0]] = 0              ' Zapamiętujemy pozycję elementu w kopcu
  parent = 0

  While 1                         ' W pętli idziemy w dół kopca, przywracając go
    leftc  = parent+parent+1  ' Pozycja lewego potomka
    rightc = leftc+1            ' Pozycja prawego potomka
    If leftc >= hlen Then Exit While ' Kończymy, jeśli lewy potomek poza kopcem
    dmin = d [h [Leftc]]      ' Wyznaczamy mniejszego potomka
    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 Exit While ' Jeśli własność kopca zachowana, kończymy
    Swap h [parent], h [pmin] ' Przywracamy własność kopca
    hp [h [parent]] = parent: hp [h [pmin]] = pmin ' na danym poziomie
    parent = pmin                 ' i przechodzimy na poziom niższy kopca
  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
    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

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

Na początek: podrozdziału strony

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.

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

Problem

Rozwiązanie

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

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

Używane struktury danych:

Dane wejściowe:

Dane wyjściowe:

Operacja z kroku 3: ustaw kopiec

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

Operacja z kroku 7: u ← korzeń kopca

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

Używane struktury danych:

Lista kroków:

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

Używane struktury danych:

Lista kroków:

Przykładowe programy

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

Problem

Rozwiązanie

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

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

Używane struktury danych:

Dane wejściowe:

Dane wyjściowe:

Operacja z kroku 3: ustaw kopiec

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

Operacja z kroku 7: u ← korzeń kopca

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

Używane struktury danych:

Lista kroków:

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

Używane struktury danych:

Lista kroków:

Przykładowe programy

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