Przeczytaj

Implementacja algorytmu Dijkstry w języku C++

W tej sekcji zapoznamy się z implementacją algorytmu Dijkstry w języku C++.

Specyfikacja problemu:

Dane:

listaSasiedztwa – lista sąsiedztwalista sąsiedztwalista sąsiedztwa spójnegograf spójnyspójnego grafu nieskierowanegograf nieskierowanynieskierowanego o dodatnich wagachwaga krawędziwagach
s – indeks wierzchołkawierzchołekwierzchołka początkowego grafu
V – liczba naturalna dodatnia; liczba wierzchołków grafu

Wynik:

tablica przechowująca najkrótsze ścieżkinajkrótsza ścieżkanajkrótsze ścieżki od wierzchołka s do pozostałych wierzchołków oraz tablica przechowująca poprzedniki kolejnych wierzchołków

Działanie programu przetestujemy dla następującego grafu:

R1KqoeFniUL5u

Ilustracja przedstawia graf z węzłami oznaczonymi literami oraz łączącymi je krawędziami oznaczone cyframi.
A, 4, C.
A, 1, B.
B, 1, E.
B, 6, G.
B, 3, F.
C, 2, D.
C, 2, G.
D, 12, F. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Przyjmijmy założenie, że wierzchołkiem początkowym jest wierzchołek E (o indeksie równym 4).

Oto lista sąsiedztwa tego grafu:

Linia 1. int listaSasiedztwa otwórz nawias kwadratowy V zamknij nawias kwadratowy otwórz nawias kwadratowy MAX podkreślnik SASIADOW zamknij nawias kwadratowy otwórz nawias kwadratowy 2 zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 2. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 2 przecinek 4 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik wierzchołek 0 otwórz nawias okrągły A zamknij nawias okrągły. Linia 3. otwórz nawias klamrowy otwórz nawias klamrowy 0 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 4 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 5 przecinek 3 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 6 przecinek 6 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik wierzchołek 1 otwórz nawias okrągły B zamknij nawias okrągły. Linia 4. otwórz nawias klamrowy otwórz nawias klamrowy 0 przecinek 4 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 3 przecinek 5 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 6 przecinek 2 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik wierzchołek 2 otwórz nawias okrągły C zamknij nawias okrągły. Linia 5. otwórz nawias klamrowy otwórz nawias klamrowy 2 przecinek 5 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 5 przecinek 12 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik wierzchołek 3 otwórz nawias okrągły D zamknij nawias okrągły. Linia 6. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik wierzchołek 4 otwórz nawias okrągły E zamknij nawias okrągły. Linia 7. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 3 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 3 przecinek 12 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik wierzchołek 5 otwórz nawias okrągły F zamknij nawias okrągły. Linia 8. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 6 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 2 przecinek 2 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy prawy ukośnik prawy ukośnik wierzchołek 6 otwórz nawias okrągły G zamknij nawias okrągły. Linia 9. zamknij nawias klamrowy średnik.

int listaSasiedztwa[V][MAX_SASIADOW][2] = {
	{{1, 1}, {2, 4}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}},  // wierzchołek 0 (A)
	{{0, 1}, {4, 1}, {5, 3}, {6, 6}, {-1, -1}, {-1, -1}},      // wierzchołek 1 (B)
	{{0, 4}, {3, 5}, {6, 2}, {-1, -1}, {-1, -1}, {-1, -1}},    // wierzchołek 2 (C)
	{{2, 5}, {5, 12}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}}, // wierzchołek 3 (D)
	{{1, 1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}},// wierzchołek 4 (E)
	{{1, 3}, {3, 12}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}}, // wierzchołek 5 (F)
	{{1, 6}, {2, 2}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}}   // wierzchołek 6 (G)
};

Już wiesz

Przypomnijmy, w jaki sposób odczytywać listę sąsiedztwa.

Dla wierzchołka A mamy dwie tablice dwuelementowe. Pierwsza to {1,1}; jej pierwszy element to indeks sąsiedniego wierzchołka, a drugi – waga krawędzi. Odczytujemy to w ten sposób, że wierzchołek A jest połączony z wierzchołkiem B krawędzią o wadze 1. Analogicznie odczytujemy kolejną parę: wierzchołek A jest połączony z wierzchołkiem C krawędzią o wadze 4.

Zapis {-1,-1} oznacza, że dany wierzchołek nie jest połączony krawędzią z wierzchołkiem o danym indeksie. W przypadku wierzchołka A widzimy, że nie ma on połączeń z kolejnymi wierzchołkami (poza B oraz C), ponieważ odpowiednie podtablice przechowują dwie wartości -1.

W naszym przypadku ważona lista sąsiedztwa (czyli lista sąsiedztwa grafu z wagami [ważonegograf ważony[ważonego]) jest tablicą trójwymiarową.

Pierwszy wymiar (V) określa liczbę wierzchołków grafu, drugi określa maksymalną liczbę sąsiadów (wartość MAX_SASIADOW obliczamy, odejmując od wartości V liczbę 1), trzeci zaś składa się z dwóch elementów – jeden służy do przechowywania indeksu wierzchołka‑sąsiada, a drugi do przechowywania wagi krawędzi prowadzącej do tego sąsiada.

Zapiszemy w języku C++ program, który dla danego grafu reprezentowanego przez listę sąsiedztwa wyświetlić dwie tablice: tablicę najkrótszych ścieżek do danych wierzchołków z wierzchołka początkowego oraz tablicę ich poprzedników.

Zaczynamy od importu niezbędnej biblioteki iostream oraz dodania obsługi przestrzeni nazw using namespace std;.

W kolejnym kroku definiujemy trzy stałe:

V – stała definiująca liczbę wierzchołków w grafie;
MAX_SASIADOW – stała, której przypisujemy różnicę wartości stałej V oraz liczby 1; wynika to z tego, że dany wierzchołek może mieć za sąsiadów maksymalnie wszystkie pozostałe wierzchołki;
NIESKONCZONOSC – stała służąca do inicjowania odległości w algorytmie Dijkstry; przypiszemy jej odpowiednio dużą wartość (minimalna przypisana wartość powinna być większa od iloczynu liczby wierzchołków oraz największej z wag krawędzi).

#include <iostream>

using namespace std;

const int V = 7;
const int MAX_SASIADOW = V - 1;
const int NIESKONCZONOSC = 10000;

Ważne!

Alternatywą dla wykorzystania zmiennej NIESKONCZONOSC jest użycie stałej INT_MAX, która dostępna jest po imporcie biblioteki <climits>.

W kolejnym kroku zapisujemy nagłówek funkcji dijkstra. Funkcja przyjmie dwa parametry:

tablicę sąsiedztwa listaSasiedztwa;
indeks wierzchołka początkowego s, czyli liczbę naturalną.

void dijkstra(int listaSasiedztwa[V][MAX_SASIADOW][2], int s) {
    
}

W programie konieczne jest zdefiniowanie tablic, z których każda pełni istotną funkcję:

d[V] – tablica długości ścieżek (liczb naturalnych); element na pozycji i oznacza aktualną długość ścieżki z wierzchołka początkowego do wierzchołka i;
p[V] – tablica poprzedników najkrótszych ścieżek (liczb naturalnych); element na pozycji i oznacza indeks poprzedniego wierzchołka na najkrótszej ścieżce do wierzchołka i; za brak poprzednika uznajemy wartość -1;
S[V] – tablica wierzchołków znajdujących się w zbiorze S (wartości logicznych); jeśli element na pozycji i jest równy true, oznacza to, że wierzchołek i znajduje się w zbiorze S; domyślnie wszystkie elementy są równe false.

Zapisujemy pętlę for. Będziemy iterować po wszystkich wierzchołkach grafu i przypisywać odpowiednie wartości tablicom. Dla każdego v-tego wierzchołka wykonamy następujące operacje:

v-temu elementowi tablicy d przypiszemy wartość NIESKONCZONOSC;
v-temu elementowi tablicy p przypiszemy wartość równą -1;
v-temu elementowi tablicy S przypiszemy wartość false.

Po wyjściu z pętli elementowi tablicy d o indeksie s przypisujemy wartość 0, ponieważ odległość wierzchołka początkowego do siebie samego wynosi 0.

#include <iostream>

using namespace std;

const int V = 7;
const int MAX_SASIADOW = V - 1;
const int NIESKONCZONOSC = 10000;

void Dijkstra(int listaSasiedztwa[V][MAX_SASIADOW][2], int s) {
	int d[V];
	int p[V];  
	bool S[V];
    
	for (v = 0; v < V; v++) {
		d[v] = NIESKONCZONOSC;
		p[v] = -1;
		S[v] = false;
	}

	d[s] = 0;
    
}

Zapisujemy pętlę for, która będzie wykonywać się tak długo, aż znajdziemy najkrótsze ścieżki i poprzedników dla wszystkich wierzchołków grafu.

#include <iostream>
#include <limits>

using namespace std;

const int V = 7;
const int MAX_SASIADOW = 6;
const int NIESKONCZONOSC =1000;

void dijkstra(int listaSasiedztwa[V][MAX_SASIADOW][2], int s) {
    int d[V];
    int p[V];
    bool S[V];

    for (int v = 0; v < V; v++) {
        d[v] = NIESKONCZONOSC;
        p[v] = -1;
        S[v] = false;
    }

    d[s] = 0;

    for (int liczbaOdwiedzonych = 0; liczbaOdwiedzonych < V; liczbaOdwiedzonych++) {
        
    }    
}

Przed rozpoczęciem przeszukiwania zmiennej u przypisujemy wartość -1, ponieważ nie wybrano jeszcze żadnego wierzchołka.

Zapisujemy zagnieżdżoną pętlę for, która będzie iterowała przez wszystkie wierzchołki. W niej umieszczamy instrukcję warunkową. By instrukcja warunkowa zwróciła wartość true, muszą zostać spełnione dwa warunki:

sprawdzany wierzchołek nie został jeszcze odwiedzony (!S[i], gdzie S to tablica wartości logicznych wskazująca, czy wierzchołek został odwiedzony);
u wciąż jest równe -1 (co oznacza, że jest to pierwszy znaleziony nieodwiedzony wierzchołek) lub tymczasowa odległość d[i] do tego wierzchołka jest mniejsza niż tymczasowa odległość d[u] do wierzchołka, który znaleźliśmy wcześniej.

Jeśli znaleźliśmy wierzchołek i, który nie został odwiedzony i ma mniejszą odległość niż obecnie wybrany wierzchołek u, to aktualizujemy u na i.

Oznaczamy wierzchołek jako odwiedzony.

#include <iostream>
#include <limits>

using namespace std;

const int V = 7;
const int MAX_SASIADOW = 6;
const int NIESKONCZONOSC =1000;

void dijkstra(int listaSasiedztwa[V][MAX_SASIADOW][2], int s) {
    int d[V];
    int p[V];
    bool S[V];

    for (int v = 0; v < V; v++) {
        d[v] = NIESKONCZONOSC;
        p[v] = -1;
        S[v] = false;
    }

    d[s] = 0;

    for (int liczbaOdwiedzonych = 0; liczbaOdwiedzonych < V; liczbaOdwiedzonych++) {
        int u = -1;

        for (int i = 0; i < V; i++) {
            if (!S[i] && (u == -1 || d[i] < d[u])) {
                u = i;
            }
        }
        
        S[u] = true; 
    }
}

Zapisujemy kolejną pętlę for, która będzie iterować po sąsiadach u-tego wierzchołka. Pętla wykonuje się dla każdego wierzchołka u, który został wybrany jako wierzchołek o obecnie najkrótszej odległości od wierzchołka początkowego, ale nie został jeszcze odwiedzony. Pętla ta ma dwa warunki:

i < MAX_SASIADOW – warunek, który zapewnia, że nie przekraczamy maksymalnej liczby możliwych sąsiadów (w przypadku pełnego grafu każdy wierzchołek miałby V - 1 sąsiadów);
listaSasiedztwa[u][i][0] != -1 – warunek, którym sprawdzamy, czy osiągnęliśmy koniec listy sąsiadów dla wierzchołka u; wartość -1 w tablicy listaSasiedztwa używana jest jako znacznik końca listy sąsiadów dla danego wierzchołka.

Dla każdego sąsiada wierzchołka u sprawdzamy, czy możemy poprawić i zaktualizować znaną odległość od wierzchołka początkowego (s) do tego sąsiada (v).

Przypisujemy zmiennej v wartość listaSasiedztwa[u][i][0], a zmiennej waga – wartość listaSasiedztwa[u][i][1].

Następnie zapisujemy instrukcję warunkową, w której sprawdzamy, czy obecna odległość do wierzchołka v (czyli wartość przechowywana w d[v]) jest większa niż suma odległości do wierzchołka u (d[u]) i wagi krawędzi między wierzchołkami u oraz v (czyli waga). Innymi słowy, czy przejście przez u do v jest krótsze niż bezpośrednie połączenie do v (jeśli takie istnieje).

Jeśli tak, oznacza to, że znaleźliśmy krótszą ścieżkę do wierzchołka v poprzez wierzchołek u. W konsekwencji aktualizujemy odległość d[v] i ustawiamy wierzchołek u jako poprzednik p[v] dla wierzchołka v.

#include <iostream>
#include <limits>

using namespace std;

const int V = 7;
const int MAX_SASIADOW = 6;  
const int NIESKONCZONOSC =1000;

void dijkstra(int listaSasiedztwa[V][MAX_SASIADOW][2], int s) {
    int d[V];
    int p[V];
    bool S[V];

    for (int v = 0; v < V; v++) {
        d[v] = NIESKONCZONOSC;
        p[v] = -1;
        S[v] = false;
    }

    d[s] = 0;

    for (int liczbaOdwiedzonych = 0; liczbaOdwiedzonych < V; liczbaOdwiedzonych++) {
        int u = -1;

        for (int i = 0; i < V; i++) {
            if (!S[i] && (u == -1 || d[i] < d[u])) {
                u = i;
            }
        }

        S[u] = true;

		for (int i = 0; i < MAX_SASIADOW && listaSasiedztwa[u][i][0] != -1; i++) {
			int v = listaSasiedztwa[u][i][0];
			int waga = listaSasiedztwa[u][i][1];

			if (d[v] > d[u] + waga) {
				d[v] = d[u] + waga;
				p[v] = u;
			}
		}
	}
}

Po wykonaniu tego fragmentu kodu dla każdego wierzchołka sąsiadującego z u mamy pewność, że odległość d[v] do niego jest najkrótszą znaną odległością, a p[v] przechowuje wierzchołek, przez który prowadzi ta najkrótsza ścieżka.

Dodajemy instrukcje odpowiedzialne za wywołanie funkcji i odpowiednie wyświetlenie wyników.

Oto kompletny kod programu:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny limits zamknij nawias ostrokątny. Linia 4. using namespace std średnik. Linia 6. const int V znak równości 7 średnik. Linia 7. const int MAX podkreślnik SASIADOW znak równości 6 średnik. Linia 8. const int NIESKONCZONOSC znak równości 1000 średnik. Linia 10. void dijkstra otwórz nawias okrągły int listaSasiedztwa otwórz nawias kwadratowy V zamknij nawias kwadratowy otwórz nawias kwadratowy MAX podkreślnik SASIADOW zamknij nawias kwadratowy otwórz nawias kwadratowy 2 zamknij nawias kwadratowy przecinek int s zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. int d otwórz nawias kwadratowy V zamknij nawias kwadratowy średnik. Linia 12. int p otwórz nawias kwadratowy V zamknij nawias kwadratowy średnik. Linia 13. bool S otwórz nawias kwadratowy V zamknij nawias kwadratowy średnik. Linia 15. for otwórz nawias okrągły int v znak równości 0 średnik v otwórz nawias ostrokątny V średnik v plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. d otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości NIESKONCZONOSC średnik. Linia 17. p otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości minus 1 średnik. Linia 18. S otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości false średnik. Linia 19. zamknij nawias klamrowy. Linia 21. d otwórz nawias kwadratowy s zamknij nawias kwadratowy znak równości 0 średnik. Linia 23. for otwórz nawias okrągły int liczbaOdwiedzonych znak równości 0 średnik liczbaOdwiedzonych otwórz nawias ostrokątny V średnik liczbaOdwiedzonych plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. int u znak równości minus 1 średnik. Linia 26. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny V średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 27. if otwórz nawias okrągły wykrzyknik S otwórz nawias kwadratowy i zamknij nawias kwadratowy ampersant ampersant otwórz nawias okrągły u znak równości znak równości minus 1 kreska pionowa kreska pionowa d otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny d otwórz nawias kwadratowy u zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. u znak równości i średnik. Linia 29. zamknij nawias klamrowy. Linia 30. zamknij nawias klamrowy. Linia 32. S otwórz nawias kwadratowy u zamknij nawias kwadratowy znak równości true średnik. Linia 34. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny MAX podkreślnik SASIADOW ampersant ampersant listaSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 0 zamknij nawias kwadratowy wykrzyknik znak równości minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 35. int v znak równości listaSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 36. int waga znak równości listaSasiedztwa otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 1 zamknij nawias kwadratowy średnik. Linia 38. if otwórz nawias okrągły d otwórz nawias kwadratowy v zamknij nawias kwadratowy zamknij nawias ostrokątny d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus waga zamknij nawias okrągły otwórz nawias klamrowy. Linia 39. d otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus waga średnik. Linia 40. p otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości u średnik. Linia 41. zamknij nawias klamrowy. Linia 42. zamknij nawias klamrowy. Linia 43. zamknij nawias klamrowy. Linia 45. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów d otwórz nawias kwadratowy V zamknij nawias kwadratowy znak równości otwórz nawias klamrowy cudzysłów średnik. Linia 46. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny V średnik i plus plus zamknij nawias okrągły. Linia 47. cout otwórz nawias ostrokątny otwórz nawias ostrokątny d otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 48. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów zamknij nawias klamrowy cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 50. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów p otwórz nawias kwadratowy V zamknij nawias kwadratowy znak równości otwórz nawias klamrowy cudzysłów średnik. Linia 51. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny V średnik i plus plus zamknij nawias okrągły. Linia 52. cout otwórz nawias ostrokątny otwórz nawias ostrokątny p otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 53. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów zamknij nawias klamrowy cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 54. zamknij nawias klamrowy. Linia 56. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 57. int listaSasiedztwa otwórz nawias kwadratowy V zamknij nawias kwadratowy otwórz nawias kwadratowy MAX podkreślnik SASIADOW zamknij nawias kwadratowy otwórz nawias kwadratowy 2 zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 58. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 2 przecinek 4 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzchołka 0 otwórz nawias okrągły A zamknij nawias okrągły. Linia 59. otwórz nawias klamrowy otwórz nawias klamrowy 0 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 4 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 5 przecinek 3 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 6 przecinek 6 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzchołka 1 otwórz nawias okrągły B zamknij nawias okrągły. Linia 60. otwórz nawias klamrowy otwórz nawias klamrowy 0 przecinek 4 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 3 przecinek 5 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 6 przecinek 2 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzchołka 2 otwórz nawias okrągły C zamknij nawias okrągły. Linia 61. otwórz nawias klamrowy otwórz nawias klamrowy 2 przecinek 5 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 5 przecinek 12 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzchołka 3 otwórz nawias okrągły D zamknij nawias okrągły. Linia 62. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzchołka 4 otwórz nawias okrągły E zamknij nawias okrągły. Linia 63. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 3 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 3 przecinek 12 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik dla wierzchołka 5 otwórz nawias okrągły F zamknij nawias okrągły. Linia 64. otwórz nawias klamrowy otwórz nawias klamrowy 1 przecinek 6 zamknij nawias klamrowy przecinek otwórz nawias klamrowy 2 przecinek 2 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy przecinek otwórz nawias klamrowy minus 1 przecinek minus 1 zamknij nawias klamrowy zamknij nawias klamrowy prawy ukośnik prawy ukośnik dla wierzchołka 6 otwórz nawias okrągły G zamknij nawias okrągły. Linia 65. zamknij nawias klamrowy średnik. Linia 67. dijkstra otwórz nawias okrągły listaSasiedztwa przecinek 4 zamknij nawias okrągły średnik. Linia 69. return 0 średnik. Linia 70. zamknij nawias klamrowy.

#include <iostream>
#include <limits>

using namespace std;

const int V = 7;
const int MAX_SASIADOW = 6;  
const int NIESKONCZONOSC =1000;

void dijkstra(int listaSasiedztwa[V][MAX_SASIADOW][2], int s) {
    int d[V];
    int p[V];
    bool S[V];

    for (int v = 0; v < V; v++) {
        d[v] = NIESKONCZONOSC;
        p[v] = -1;
        S[v] = false;
    }

    d[s] = 0;

    for (int liczbaOdwiedzonych = 0; liczbaOdwiedzonych < V; liczbaOdwiedzonych++) {
        int u = -1;

        for (int i = 0; i < V; i++) {
            if (!S[i] && (u == -1 || d[i] < d[u])) {
                u = i;
            }
        }

        S[u] = true;

		for (int i = 0; i < MAX_SASIADOW && listaSasiedztwa[u][i][0] != -1; i++) {
			int v = listaSasiedztwa[u][i][0];
			int waga = listaSasiedztwa[u][i][1];

			if (d[v] > d[u] + waga) {
				d[v] = d[u] + waga;
				p[v] = u;
			}
		}
	}

	cout << "d[V] = { ";
	for (int i = 0; i < V; i++)
		cout << d[i] << " ";
	cout << "}" << endl;

	cout << "p[V] = { ";
	for (int i = 0; i < V; i++)
		cout << p[i] << " ";
	cout << "}" << endl;
}

int main() {
	int listaSasiedztwa[V][MAX_SASIADOW][2] = {
	    {{1, 1}, {2, 4}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}},  // dla wierzchołka 0 (A)
	    {{0, 1}, {4, 1}, {5, 3}, {6, 6}, {-1, -1}, {-1, -1}},      // dla wierzchołka 1 (B)
	    {{0, 4}, {3, 5}, {6, 2}, {-1, -1}, {-1, -1}, {-1, -1}},    // dla wierzchołka 2 (C)
	    {{2, 5}, {5, 12}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}}, // dla wierzchołka 3 (D)
	    {{1, 1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}},// dla wierzchołka 4 (E)
	    {{1, 3}, {3, 12}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}}, // dla wierzchołka 5 (F)
	    {{1, 6}, {2, 2}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}}   // dla wierzchołka 6 (G)
	};

	dijkstra(listaSasiedztwa, 4);

	return 0;
}

Wynik działania programu dla analizowanego grafu:

d[V] = { 2 1 6 11 0 4 7 }
p[V] = { 1 4 0 2 -1 1 1 }

Polecenie 1

Spróbuj ręcznie zweryfikować poprawność uzyskanego rozwiązania.

Słownik

długość ścieżki (koszt dojścia)

suma wag wszystkich krawędzi, z których składa się ścieżka, droga lub cykl

graf nieskierowany

graf, którego połączone krawędziami wierzchołki nie mają ustalonego kierunku, w którym można się po nich poruszać (są nieuporządkowane)

graf spójny

graf, w którym każda para wierzchołków połączona jest drogą

graf ważony

graf którego krawędzie mają przypisane wagi

krawędź

nieuporządkowana para (niekoniecznie różnych) elementów zbioru wierzchołków, tj. takich, które są ze sobą połączone; w reprezentacji graficznej jest to linia łącząca te wierzchołki; krawędź może łączyć ze sobą jeden wierzchołek (wtedy nazywana jest pętlą)

lista sąsiedztwa

zestaw V uporządkowanych list, gdzie lista o indeksie i jest listą wszystkich sąsiadów wierzchołka i

najkrótsza ścieżka

taka ścieżka łącząca dwa wierzchołki grafu, której suma wag krawędzi jest jak najmniejsza

stopień wierzchołka

liczba krawędzi incydentnych z danym wierzchołkiem

waga krawędzi

wartość przypisana krawędzi grafu

wierzchołek

inaczej: punkt, węzeł; element niepustego zbioru, który wraz ze zbiorem krawędzi tworzy graf

Wprowadzenie

Prezentacja multimedialna

Implementacja algorytmu Dijkstry w języku C++

Słownik