Implementacja - I_R_W14_M38_C++ Podejście zachłanne. Najkrótsza droga w grafie

R1GJG6M5BA9OA

Implementacja algorytmu Dijkstry w języku C++

Program oblicza najkrótsze ścieżki od wybranego wierzchołka początkowego do wszystkich pozostałych wierzchołków grafu oraz zapisuje poprzedniki, dzięki którym można odtworzyć przebieg ścieżki.

Specyfikacja problemu:

Dane:

listaSasiedztwa – tablica opisująca graf nieskierowany i ważony;

Każdy element listaSasiedztwa[u][i]jest trójką:

indeks sąsiada wierzchołka u,
waga krawędzi prowadzącej z u do tego sąsiada,
lub {-1, -1}, jeśli brak połączenia.

s – numer wierzchołka startowego,

V– liczba wierzchołków w grafie.

Wynik:

d[] - tablica najkrótszych odległości od wierzchołka startowego,
p[] - tablica poprzedników, która pozwala odtworzyć najkrótszą ścieżkę.

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

Opis działania algorytmu

Inicjalizacja
- Wszystkie odległości ustawiane są na wartość „nieskończoność”.
- Dla wierzchołka startowego s ustawiamy d[s] = 0.
- Tablica poprzedników p[] wypełniona jest wartościami -1.
- Tablica S[] oznacza, które wierzchołki zostały już odwiedzone.
Wybór wierzchołka o najmniejszym koszcie
- Algorytm wybiera wierzchołek u, który:
  - nie został jeszcze odwiedzony,
  - ma najmniejszą wartość d[u].
Dodanie wierzchołka do zbioru S
- Wierzchołek u zostaje oznaczony jako odwiedzony.
Relaksacja krawędzi
- Dla każdego sąsiada v wierzchołka u sprawdzamy, czy:
- Jeśli tak:
  - aktualizujemy koszt d[v],
  - ustawiamy poprzednika p[v] = u.
Zakończenie
- Po odwiedzeniu wszystkich wierzchołków algorytm zwraca tablice d[] i p[].

Algorytm Dijkstry działa zachłannie: w każdej iteracji wybiera wierzchołek o najmniejszej aktualnej odległości, który nie został jeszcze odwiedzony. Następnie wykonuje relaksację krawędzi, czyli sprawdza, czy przejście przez ten wierzchołek prowadzi do skrócenia drogi do jego sąsiadów.

Proces powtarza się, aż wszystkie wierzchołki zostaną odwiedzone lub nie ma już dostępnych wierzchołków.

Reprezentacja grafu

W programie graf jest zapisany jako macierz sąsiedztwa:

int waga[V][V];

Każdy element macierzy oznacza wagę krawędzi między wierzchołkami:

jeśli waga[u][v] > 0 → istnieje krawędź z u do v o tej wadze,
jeśli waga[u][v] == 0 → brak połączenia.

Ponieważ graf jest nieskierowany, macierz jest symetryczna:

waga[u][v] == waga[v][u]

Oto macierz sąsiedztwa grafu z naszego przykładu:

int waga[V][V] = {
    {0,1,4,0,0,0,0},
    {1,0,0,0,1,3,6},
    {4,0,0,5,0,0,2},
    {0,0,5,0,0,12,0},
    {0,1,0,0,0,0,0},
    {0,3,0,12,0,0,0},
    {0,6,2,0,0,0,0}
};

Interpretacja:

waga[0][1] = 1 → krawędź 0–1 o wadze 1
waga[0][2] = 4 → krawędź 0–2 o wadze 4
waga[1][4] = 1 → krawędź 1–4 o wadze 1
waga[3][5] = 12 → krawędź 3–5 o wadze 12
waga[u][v] = 0 → brak krawędzi

Kod w C++:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. using namespace std średnik. Linia 4. const int V znak równości 7 średnik. Linia 5. const int INF znak równości 1000 średnik. Linia 7. void Dijkstra otwórz nawias okrągły int waga otwórz nawias kwadratowy V zamknij nawias kwadratowy otwórz nawias kwadratowy V zamknij nawias kwadratowy przecinek int s zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. int d otwórz nawias kwadratowy V zamknij nawias kwadratowy średnik. Linia 9. int p otwórz nawias kwadratowy V zamknij nawias kwadratowy średnik. Linia 10. bool S otwórz nawias kwadratowy V zamknij nawias kwadratowy średnik. Linia 12. prawy ukośnik prawy ukośnik Inicjalizacja. Linia 13. 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 14. d otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości INF średnik. Linia 15. p otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości minus 1 średnik. Linia 16. S otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości false średnik. Linia 17. zamknij nawias klamrowy. Linia 19. d otwórz nawias kwadratowy s zamknij nawias kwadratowy znak równości 0 średnik. Linia 21. prawy ukośnik prawy ukośnik Główna pętla algorytmu. Linia 22. for otwórz nawias okrągły int k znak równości 0 średnik k otwórz nawias ostrokątny V średnik k plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. prawy ukośnik prawy ukośnik Wybór wierzchołka o najmniejszym koszcie. Linia 25. 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. if otwórz nawias okrągły u znak równości znak równości minus 1 zamknij nawias okrągły break średnik. Linia 33. S otwórz nawias kwadratowy u zamknij nawias kwadratowy znak równości true średnik. Linia 35. prawy ukośnik prawy ukośnik Relaksacja krawędzi wychodzących z u. Linia 36. 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 37. if otwórz nawias okrągły waga otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy prawy ukośnik prawy ukośnik istnieje krawędź u→v. Linia 38. int w znak równości waga otwórz nawias kwadratowy u zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy średnik. Linia 39. if otwórz nawias okrągły wykrzyknik S otwórz nawias kwadratowy v zamknij nawias kwadratowy ampersant ampersant d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus w otwórz nawias ostrokątny d otwórz nawias kwadratowy v zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. d otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości d otwórz nawias kwadratowy u zamknij nawias kwadratowy plus w średnik. Linia 41. p otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości u średnik. Linia 42. zamknij nawias klamrowy. Linia 43. zamknij nawias klamrowy. Linia 44. zamknij nawias klamrowy. Linia 45. zamknij nawias klamrowy. Linia 47. prawy ukośnik prawy ukośnik Wyniki. Linia 48. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów d dwukropek cudzysłów średnik. Linia 49. 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 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 50. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów lewy ukośnik np dwukropek 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 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 52. zamknij nawias klamrowy. Linia 54. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 55. int waga otwórz nawias kwadratowy V zamknij nawias kwadratowy otwórz nawias kwadratowy V zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 56. otwórz nawias klamrowy 0 przecinek 1 przecinek 4 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 57. otwórz nawias klamrowy 1 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 3 przecinek 6 zamknij nawias klamrowy przecinek. Linia 58. otwórz nawias klamrowy 4 przecinek 0 przecinek 0 przecinek 5 przecinek 0 przecinek 0 przecinek 2 zamknij nawias klamrowy przecinek. Linia 59. otwórz nawias klamrowy 0 przecinek 0 przecinek 5 przecinek 0 przecinek 0 przecinek 12 przecinek 0 zamknij nawias klamrowy przecinek. Linia 60. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 61. otwórz nawias klamrowy 0 przecinek 3 przecinek 0 przecinek 12 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek. Linia 62. otwórz nawias klamrowy 0 przecinek 6 przecinek 2 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy. Linia 63. zamknij nawias klamrowy średnik. Linia 65. Dijkstra otwórz nawias okrągły waga przecinek 4 zamknij nawias okrągły średnik. Linia 66. zamknij nawias klamrowy.

#include <iostream>
using namespace std;

const int V = 7;
const int INF = 1000;

void Dijkstra(int waga[V][V], int s) {
    int d[V];
    int p[V];
    bool S[V];

    // Inicjalizacja
    for (int i = 0; i < V; i++) {
        d[i] = INF;
        p[i] = -1;
        S[i] = false;
    }

    d[s] = 0;

    // Główna pętla algorytmu
    for (int k = 0; k < V; k++) {

        // Wybór wierzchołka o najmniejszym koszcie
        int u = -1;
        for (int i = 0; i < V; i++) {
            if (!S[i] && (u == -1 || d[i] < d[u])) {
                u = i;
            }
        }

        if (u == -1) break;
        S[u] = true;

        // Relaksacja krawędzi wychodzących z u
        for (int v = 0; v < V; v++) {
            if (waga[u][v] > 0) {        // istnieje krawędź u→v
                int w = waga[u][v];
                if (!S[v] && d[u] + w < d[v]) {
                    d[v] = d[u] + w;
                    p[v] = u;
                }
            }
        }
    }

    // Wyniki
    cout << "d: ";
    for (int i = 0; i < V; i++) cout << d[i] << " ";
    cout << "\np: ";
    for (int i = 0; i < V; i++) cout << p[i] << " ";
}

int main() {
    int waga[V][V] = {
        {0,1,4,0,0,0,0},
        {1,0,0,0,1,3,6},
        {4,0,0,5,0,0,2},
        {0,0,5,0,0,12,0},
        {0,1,0,0,0,0,0},
        {0,3,0,12,0,0,0},
        {0,6,2,0,0,0,0}
    };

    Dijkstra(waga, 4);
}

Wynik działania programu

d[] = 2 1 6 11 0 4 7
p[] = 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

Algorytm Dijkstry - pseudokod

Strefa wyzwań