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


Tematy pokrewne  
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie
 

Problem

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

 

 

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:  034
ścieżka nr 2:  0 134
ścieżka nr 3:  0 1234
ścieżka nr 4:  0 124
 

 

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:  034
ścieżka nr 2:
 0134
ścieżka nr 3:
 01234
ścieżka nr 4:  0 124

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:

 

            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:

 

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 symbol 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 symbol 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 symbol 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 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 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(n2). Jednakże dużo lepszym pomysłem (ale trudniejszym w realizacji) jest zastosowanie kolejki priorytetowej opartej na strukturze kopca.

 

Program

Ważne:

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.

 

Przykładowe dane:

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
 
Lazarus
// Algorytm Dijkstry z wyszukiwaniem liniowym
// Data: 15.03.2014
// (C)2014 mgr Jerzy Wałaszek
//-------------------------------------------

program dijkstra;

// Typy danych

type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    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 PslistEl;      // Tablica list sąsiedztwa
  pw,rw : PslistEl;

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.
Code::Blocks
// Algorytm Dijkstry z wyszukiwaniem liniowym
// Data: 15.03.2014
// (C)2014 mgr Jerzy Wałaszek
//-------------------------------------------

#include <iostream>

using namespace std;

// Typy danych

struct slistEl
{
  slistEl * 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
  slistEl **graf;                 // Tablica list sąsiedztwa
  slistEl *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 slistEl * [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 slistEl;             // 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;
}
Free Basic
' Algorytm Dijkstry z wyszukiwaniem liniowym
' Data: 15.03.2014
' (C)2014 mgr Jerzy Wałaszek
'-------------------------------------------

' Typy danych

Type slistEl
  Dim As slistEl 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 slistEl Ptr Ptr graf      ' Tablica list sąsiedztwa
Dim As slistEl 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 slistEl 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 slistEl                ' 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 symbol 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 wykonaj: 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 symbol graf, 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: hlenn
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: uh[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];  hlenhlen - 1
K02: hp[ h[0] ] ← 0
K03: parent ← 0
K04:     left ← 2 x parent + 1;  rightleft + 1
K05:     Jeśli left hlen, to zakończ
K06:     dmind[ h[left] ];  pminleft
K07:     Jeśli right hlen, to idź do kroku K09
K08:     Jeśli dmin > d[ h[right] ], to  dmind[ h[right] ];   pminright
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:     parentpmin
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:     childparent
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.

Program

Ważne:

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.

 

Przykładowe dane:

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
 
Lazarus
// Algorytm Dijkstry z kolejką priorytetową
// Data: 16.03.2014
// (C)2014 mgr Jerzy Wałaszek
//-----------------------------------------

program dijkstra;

// Typy danych

type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    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 PslistEl;      // Tablica list sąsiedztwa
  pw,rw : PslistEl;

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.
Code::Blocks
// Algorytm Dijkstry z kolejką priorytetową
// Data: 16.03.2014
// (C)2014 mgr Jerzy Wałaszek
//-----------------------------------------

#include <iostream>

using namespace std;

// Typy danych

struct slistEl
{
  slistEl * 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,hlen,parent,left,right,dmin,pmin,child,*d,*p,*S,*h,*hp;
  bool *QS;                       // Zbiory Q i S
  slistEl **graf;                 // Tablica list sąsiedztwa
  slistEl *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 slistEl * [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 slistEl;             // 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;
}
Free Basic
' Algorytm Dijkstry z kolejką priorytetową
' Data: 16.03.2014
' (C)2014 mgr Jerzy Wałaszek
'-----------------------------------------

' Typy danych

Type slistEl
  Dim As slistEl 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 slistEl Ptr Ptr graf      ' Tablica list sąsiedztwa
Dim As slistEl 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 slistEl 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 slistEl                ' 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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.