Rozważ przykład znalezienia najkrótszej ścieżki. Podano sieć autostrad łączących regiony miasta. Niektóre drogi są jednokierunkowe. Znajdź najkrótsze ścieżki z centrum miasta do każdego miasta w okolicy.
Aby rozwiązać ten problem, możesz użyć Algorytm Dijkstry- algorytm na wykresach, wynaleziony przez holenderskiego naukowca E. Dijkstrę w 1959 roku. Znajduje najkrótszą odległość od jednego z wierzchołków wykresu do wszystkich pozostałych. Działa tylko dla wykresów bez krawędzi o ujemnej wadze.
Niech będzie wymagane znalezienie najkrótszych odległości od pierwszego wierzchołka do wszystkich pozostałych.
Koła oznaczają wierzchołki, linie oznaczają ścieżki między nimi (krawędzie wykresu). Numery wierzchołków są wskazane w kółkach, ich waga jest podana nad krawędziami - długość ścieżki. Obok każdego wierzchołka zaznaczona jest czerwona etykieta - długość najkrótszej ścieżki do tego wierzchołka z wierzchołka 1.
Zakłada się, że etykieta samego wierzchołka 1 wynosi 0, etykiety pozostałych wierzchołków są nieosiągalne duża liczba(najlepiej - nieskończoność). Odzwierciedla to, że odległości od wierzchołka 1 do innych wierzchołków nie są jeszcze znane. Wszystkie wierzchołki wykresu są oznaczone jako nieodwiedzone. 
Pierwszy krok
Wierzchołek 1 ma etykietę minimum. Wierzchołki 2, 3 i 6 są jego sąsiadami. Po kolei omijamy sąsiadów wierzchołka.
Pierwszym sąsiadem wierzchołka 1 jest wierzchołek 2, ponieważ długość ścieżki do niego jest minimalna. Długość ścieżki do niego przez wierzchołek 1 jest równa sumie najkrótszej odległości do wierzchołka 1, wartości jego etykiety i długości krawędzi od 1 do 2, czyli 0 + 7 = 7. To mniej niż aktualna etykieta wierzchołka 2 (10000), więc nowa etykieta drugiego wierzchołka to 7. 
Podobnie znajdujemy długości ścieżek dla wszystkich innych sąsiadów (wierzchołki 3 i 6).
Wszyscy sąsiedzi węzła 1 są sprawdzani. Obecna minimalna odległość do szczytu 1 jest uważana za ostateczną i nie podlega rewizji. Wierzchołek 1 jest oznaczony jako odwiedzony.
Drugi krok
Krok 1 algorytmu jest powtarzany. Ponownie znajdujemy „najbliższy” z nieodwiedzonych wierzchołków. To jest wierzchołek 2 oznaczony jako 7.
Ponownie próbujemy zredukować etykiety sąsiadów wybranego wierzchołka, próbując przejść przez nie przez drugi wierzchołek. Sąsiadami wierzchołka 2 są wierzchołki 1, 3 i 4.
Vertex 1 został już odwiedzony. Następnym sąsiadem wierzchołka 2 jest wierzchołek 3, ponieważ ma minimalną etykietę wierzchołków oznaczonych jako nieodwiedzone. Jeśli przejdziesz do niego przez 2, długość takiej ścieżki będzie równa 17 (7 + 10 = 17). Ale obecna etykieta trzeciego wierzchołka to 9 i 9< 17, поэтому метка не меняется.
Kolejnym sąsiadem wierzchołka 2 jest wierzchołek 4. Jeśli przejdziemy do niego przez drugi, to długość takiej ścieżki będzie równa 22 (7 + 15 = 22). Od 22<10000, устанавливаем метку вершины 4 равной 22.
Wszyscy sąsiedzi wierzchołka 2 zostali wyświetleni, więc oznaczamy go jako odwiedzony.
Trzeci krok
Powtarzamy krok algorytmu wybierając wierzchołek 3. Po jego „przetworzeniu” otrzymujemy następujące wyniki. 
Czwarty krok
Piąty krok
szósty krok
Zatem najkrótsza ścieżka od wierzchołka 1 do wierzchołka 5 będzie ścieżką przez wierzchołki 1 — 3 — 6 — 5
, ponieważ w ten sposób zyskujemy minimalną wagę 20.
Przyjrzyjmy się najkrótszej ścieżce. Znamy długość ścieżki dla każdego wierzchołka, a teraz rozważymy wierzchołki od końca. Rozważmy końcowy wierzchołek (w tym przypadku wierzchołek 5
) i dla wszystkich wierzchołków, z którymi jest połączony, znajdujemy długość ścieżki, odejmując wagę odpowiedniej krawędzi od długości ścieżki końcowego wierzchołka.
Tak, góra 5
ma długość ścieżki 20
. Ona jest połączona z szczytem 6
oraz 4
.
Na górę 6
weź wagę 20 - 9 = 11 (dopasowane).
Na górę 4
weź wagę 20 - 6 = 14 (nie pasuje).
Jeśli w rezultacie otrzymamy wartość, która odpowiada długości ścieżki danego wierzchołka (w tym przypadku wierzchołek 6
), to z niego powstało przejście do końcowego wierzchołka. Zaznaczamy ten wierzchołek na żądanej ścieżce.
Następnie wyznaczamy krawędź, przez którą dotarliśmy do wierzchołka 6
. I tak dalej, aż dojdziemy do początku.
Jeżeli w wyniku takiego trawersu na jakimś kroku będziemy mieli te same wartości dla kilku wierzchołków, to możemy wziąć dowolny z nich – kilka ścieżek będzie miało tę samą długość.
Implementacja algorytmu Dijkstry
Do przechowywania wag wykresów używana jest macierz kwadratowa. Wierzchołki wykresu znajdują się w nagłówkach wierszy i kolumn. A wagi łuków wykresu są umieszczane w wewnętrznych komórkach tabeli. Wykres nie zawiera pętli, więc główna przekątna macierzy zawiera wartości zerowe.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 7 | 9 | 0 | 0 | 14 |
| 2 | 7 | 0 | 10 | 15 | 0 | 0 |
| 3 | 9 | 10 | 0 | 11 | 0 | 2 |
| 4 | 0 | 15 | 11 | 0 | 6 | 0 |
| 5 | 0 | 0 | 0 | 6 | 0 | 9 |
| 6 | 14 | 0 | 2 | 0 | 9 | 0 |
Implementacja w C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#define _CRT_SECURE_NO_WARNINGS
#włączać
#włączać
#define ROZMIAR 6
int main()
{
int; // macierz połączeń
int d; // minimalna odległość
w telewizji; // odwiedzone wierzchołki
temp. wewn., miniindeks, min;
int początek_indeks = 0;
system("chcp 1251" );
system("cls" );
// Inicjalizacja macierzy relacji
dla (int i = 0; i
a[i][i] = 0;
dla (int j = i + 1; j
scanf("%d" , &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
// Wyświetl macierz relacji
dla (int i = 0; i
dla (int j = 0; j
printf("\n");
}
//Zainicjuj wierzchołki i odległości
dla (int i = 0; i
d[i] = 10000;
v[i] = 1;
}
d=0;
// Krok algorytmu
robić(
miniindeks = 10000;
min = 10000;
dla (int i = 0; i
jeśli ((v[i] == 1) && (d[i]
min = d[i];
miniindeks = i;
}
}
// Dodaj znalezioną minimalną wagę
// do aktualnej wagi wierzchołków
// i porównaj z aktualną minimalną wagą wierzchołków
jeśli (minindeks != 10000)
{
dla (int i = 0; i
jeśli (a[i] > 0)
{
temp = min + a[i];
jeśli (temp< d[i])
{
d[i] = temp;
}
}
}
v = 0;
}
) podczas (minindeks< 10000);
// Wypisz najkrótsze odległości do wierzchołków
drukujf( "\nNajkrótsze odległości do wierzchołków: \n");
dla (int i = 0; i
// Przywróć ścieżkę
inwerter; // tablica odwiedzonych wierzchołków
int koniec = 4; // indeks wierzchołka końcowego = 5 - 1
ver = koniec + 1; // element początkowy - wierzchołek końcowy
int k = 1; // indeks poprzedniego szczytu
int waga = d; // waga końca wierzchołka
while (koniec != begin_index) // aż dojdziemy do wierzchołka początkowego
{
dla (int i = 0; i
jeśli (a[i] != 0) // jeśli istnieje połączenie
{
int temp = waga - a[i]; // określ wagę ścieżki z poprzedniego wierzchołka
if (temp == d[i]) // jeśli waga zgadza się z obliczoną
{ // oznacza to, że nastąpiło przejście z tego wierzchołka
waga = temperatura; // zapisz nową wagę
koniec=i; // zapisz poprzedni wierzchołek
ver[k] = i + 1; // i zapisz to do tablicy
k++;
}
}
}
// Wyświetlenie ścieżki (początkowy wierzchołek znajduje się na końcu tablicy k elementów)
drukujf( "\nWyjściowa najkrótsza ścieżka\n");
dla (int i = k - 1; i >= 0; i--)
printf("%3d" , ver[i]);
getchar(); getchar();
zwróć 0;
}
Wynik wykonania
Z powrotem:
Algorytm Dijkstry to algorytm grafowy wymyślony przez holenderskiego naukowca E. Dijkstrę w 1959 r. Znajduje najkrótszą odległość od jednego z wierzchołków grafu do wszystkich pozostałych. Algorytm działa tylko dla grafów bez krawędzi o ujemnej wadze. Algorytm jest szeroko stosowany w programowaniu i technologiach, takich jak OSPF, wykorzystuje go do eliminacji tras pętli zwrotnych, znanych również jako najkrótsza ścieżka.
Algorytm Dijkstry rozwiązuje problem najkrótszej ścieżki z jednym wierzchołkiem dla ważonego grafu skierowanego G = (V, E) z początkowym wierzchołkiem s, w którym wagi wszystkich krawędzi są nieujemne ((u, v) ? 0 dla wszystkich (u , v) E). W przypadku, gdy krawędzie grafu nie są równe, wskazane jest zastosowanie tego algorytmu.
Formułowanie zadań. Jest wykres. Niektóre z jego wierzchołków są oznaczone jako wierzchołek 1. Konieczne jest znalezienie minimalnych ścieżek od wierzchołka 1 do każdego z wierzchołków wykresu. Ścieżka minimalna to ścieżka z minimalną sumą cen wzdłuż ścieżki. Cena jest liczbą nieujemną, która jest wagą krawędzi.
Idea algorytmu. Pomysł opiera się na następującym oczywistym stwierdzeniu: Niech minimalna ścieżka od wierzchołka a do wierzchołka B. I niech wierzchołek B będzie połączony z pewną liczbą wierzchołków i . Oznacz przez C i koszt ścieżki od wierzchołka B do wierzchołka i. Wybierzmy minimalną wartość z C i. Wtedy minimalna kontynuacja ścieżki z punktu B przejdzie przez wybraną wartość.
To stwierdzenie tak naprawdę nie wymaga dowodu. I wynika z tego bardzo poważna konsekwencja. Niech będzie zbiór wierzchołków, przez które przechodzą już minimalne ścieżki. Taki zbiór jest gwarantowany, jest to wierzchołek 1. Sformułowane powyżej zdanie umożliwia dodanie jeszcze jednego wierzchołka do już istniejącego zbioru wierzchołków (będziemy je dalej nazywać wybranymi), a ponieważ liczba wierzchołków na grafie jest skończony, to w skończonej liczbie kroków zostaną wybrane wszystkie wierzchołki grafu i to będzie rozwiązanie.
Istotą algorytmu Dijkstry jest procedura dodawania jeszcze jednego wierzchołka do zbioru wybranych. Ta procedura składa się z dwóch kroków:
1. Budujemy zbiór wierzchołków nachodzących na wybrany i znajdujemy wśród nich wierzchołek o najniższej cenie. Znaleziony wierzchołek jest dodawany do zbioru wybranych.
2. Konstruujemy zbiór wierzchołków nachodzących na wybrany i ustalamy dla nich nowe ceny. Nowa cena wierzchołka to minimalny koszt ścieżki od zbioru wybranych wierzchołków do danego wierzchołka. Nowa cena jest zbudowana w następujący sposób:
a. Dla niewybranego wierzchołka w zbiorze wybranych wierzchołków określany jest podzbiór wierzchołków, które są z nim powiązane.
b. Dla każdego wierzchołka wybranego podzbioru określany jest koszt ścieżki do danego.
c. Określana jest cena minimalna. Ta cena staje się ceną najwyższą.
Algorytm działa z dwoma rodzajami cen: ceną krawędziową i ceną najwyższą. Ceny brzegowe są stałe. Ceny szczytów są stale przeliczane. Znaczenie tych cen jest inne. Koszt krawędzi to koszt przejścia z wierzchołka do wierzchołka połączonego tą krawędzią. A cena szczytu to cena ścieżki minimalnej. Kolejna ważna uwaga dotyczy przeliczenia cen wstępnych. W rzeczywistości ma sens przeliczanie cen wstępnych tylko dla tych wierzchołków, które są powiązane z wierzchołkiem dodanym do zbioru wybranych w ostatnim kroku, ponieważ dla innych wierzchołków nie ma powodu, aby zmieniać cenę wstępną.
Wiadomo, że wszystkie ceny (na przykład ułożenie ścieżki lub przejścia) są nieujemne. Znajdź ścieżkę o najniższym koszcie 1->i dla wszystkich i=1. n w czasie O(n2).
W trakcie działania algorytmu wybrane zostaną niektóre miasta (na początku tylko miasto 1, na końcu wszystkie). W którym:
dla każdego wybranego miasta i przechowywany jest najmniejszy koszt ścieżki 1->i; jednocześnie wiadomo, że minimum osiąga się na ścieżce przechodzącej tylko przez wybrane miasta;
dla każdego nieprzydzielonego miasta i przechowywana jest ścieżka o najniższym koszcie 1->i, w której tylko wybrane miasta są używane jako miasta pośrednie.
Zbiór alokowanych miast rozszerzamy o następującą uwagę: jeśli spośród wszystkich nieprzydzielonych miast weźmiemy to, dla którego zapisana liczba jest minimalna, to ta liczba jest rzeczywiście najmniejszym kosztem. Rzeczywiście, niech będzie krótsza droga. Rozważ pierwsze niewybrane miasto na tej ścieżce - droga do niego jest już dłuższa! (Niezbędna jest tutaj negatywność cen.)
Dodając wybrane miasto do wybranych, musimy poprawić informacje zapisane dla miast niewybranych. W tym przypadku wystarczy wziąć pod uwagę tylko ścieżki, w których nowe miasto jest ostatnim punktem przesiadkowym, a jest to łatwe, ponieważ znamy już minimalny koszt trasy do nowego miasta.
Innymi słowy, każdy wierzchołek od V jest powiązany z etykietą - minimalna znana odległość od tego wierzchołka do a. Algorytm działa krok po kroku - na każdym kroku "odwiedza" jeden wierzchołek i próbuje zredukować etykiety. Algorytm kończy się po odwiedzeniu wszystkich wierzchołków.
Inicjalizacja. Górna etykieta a ma być równy 0 , etykiety pozostałych wierzchołków to nieskończoność. Odzwierciedla to, że odległości od a do innych szczytów są nadal nieznane. Wszystkie wierzchołki wykresu są oznaczone jako nieodwiedzone.
Krok algorytmu. Jeśli wszystkie wierzchołki zostały odwiedzone, algorytm kończy działanie. W przeciwnym razie wierzchołek jest wybierany z wierzchołków jeszcze nieodwiedzonych ty Z etykietą minimum. Rozważamy wszystkie możliwe trasy, w których ty jest przedostatnim punktem. Wierzchołki połączone z wierzchołkiem ty krawędzie, nazwiemy sąsiadów tego wierzchołka. Dla każdego sąsiada rozważ nową długość ścieżki równą sumie bieżącej etykiety ty i długość połączenia krawędzi ty z tym sąsiadem. Jeśli wynikowa długość jest mniejsza niż etykieta sąsiada, zastąp etykietę tą długością. Po rozważeniu wszystkich sąsiadów zaznaczamy wierzchołek ty zgodnie z odwiedzinami i powtórz krok.
Ponieważ algorytm Dijkstry za każdym razem wybiera przetwarzanie wierzchołka z najmniejszym oszacowaniem najkrótszej ścieżki, możemy powiedzieć, że należy on do algorytmów zachłannych.
Opiszmy bardziej szczegółowo, jak działa algorytm Dijkstry.
Algorytm wykorzystuje trzy tablice liczb N (= liczba wierzchołków sieci) każda. Pierwsza tablica A zawiera etykiety z dwiema wartościami: 0 (wierzchołek jeszcze nie uwzględniony) i 1 (wierzchołek już uwzględniony); druga tablica B zawiera odległości - bieżące najkrótsze odległości od odpowiedniego wierzchołka; trzecia tablica c zawiera numery wierzchołków - k-ty element C [k] to numer przedostatniego wierzchołka na najkrótszej bieżącej ścieżce z Vi do Vk. Macierz odległości D określa długość łuku D ; jeśli nie ma takiego łuku, to D otrzymuje dużą liczbę B, równą „nieskończoności maszyny”.
Teraz możemy opisać:
1. (inicjalizacja). W cyklu od 1 do N wypełnij tablicę A zerami; wypełnij tablicę C liczbą i; przenieś i-ty wiersz macierzy D do tablicy B, A [i]: =1; C [i]: =0 (i - początkowy numer wierzchołka)
2. (krok ogólny). Znajdź minimum wśród nieoznaczonych (czyli tych k, dla których A [k] = 0); niech minimum zostanie osiągnięte przy indeksie j, tj. B[j]<=B [k] Затем выполняются следующие операции: A [j]: =1; если B [k] >B [j] +D , wtedy (B [k]: =B [j] +D ; C [k]: =j) (Warunek oznacza, że ścieżka Vi. Vk jest dłuższa niż ścieżka Vi. Vj Vk) . (Jeżeli wszystkie A [k] są zaznaczone, to długość ścieżki od Vi do Vk jest równa B [k]. Teraz musimy) policzyć wierzchołki zawarte w najkrótszej ścieżce).
3. (wydanie odpowiedzi). (Ścieżka z Vi do Vk jest zwracana w odwrotnej kolejności według następującej procedury:)
2. Wydanie z;
3. z:=C[z]. Jeśli z = 0, to koniec, w przeciwnym razie przejdź do 3.2.
Do wykonania algorytmu konieczne jest przeskanowanie tablicy B N elementów N razy, tj. Algorytm Dijkstry ma złożoność kwadratową: O(n2).
Poniżej znajduje się schemat blokowy algorytmu Dijkstry (patrz rys. 2).
Rys.2. Schemat blokowy algorytmu Dijkstry
Na początku algorytmu odległość dla początkowego wierzchołka jest ustawiona na zero, a wszystkie pozostałe odległości są wypełniane dużą liczbą dodatnią (większą niż maksymalna możliwa ścieżka na wykresie). Tablica flags jest wypełniona zerami. Wtedy zaczyna się główna pętla.
Na każdym kroku pętli szukamy wierzchołka o minimalnej odległości i flagi równej zero. Następnie ustawiamy w nim flagę na 1 i sprawdzamy wszystkie sąsiadujące z nią wierzchołki. Jeśli odległość w nim jest większa niż suma odległości do bieżącego wierzchołka i długości krawędzi, zmniejszamy ją. Pętla kończy się, gdy flagi wszystkich wierzchołków staną się równe 1.
Do każdego miasta regionu (jeśli możesz poruszać się tylko po drogach).
Opcja 2. Istnieje wiele lotów między miastami świata, każdy koszt jest znany. Koszt lotu z punktu A do punktu B może nie być równy kosztowi lotu z punktu B do punktu A. Znajdź trasę o minimalnym koszcie (ewentualnie z przesiadkami) z Kopenhagi do Barnauł.
Formalna definicja
Przykład
Rozważ wykonanie algorytmu na przykładzie wykresu pokazanego na rysunku.
Niech będzie wymagane znalezienie najkrótszych odległości od pierwszego wierzchołka do wszystkich pozostałych.
Implementacje w językach programowania
Wykonanie w języku C (C)
#define ROZMIAR 6 #define INF 1000000000 int a [ROZMIAR ][ROZMIAR] = (( INF , 5 , INF , INF , INF , INF ),( 1 , 2 , 3 , 4 , 5 , 6 ), // macierz ścieżki ( 1 , 2 , 3 , 4 , 5 , 6 ),( 1 , 2 , 3 , 4 , 5 , 6 ), // indeksy poziome od punktu { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // pionowo do punktu, wartość - waga int d[ ROZMIAR ]; // tablica znalezionych najkrótszych ścieżek, indeksy - wierzchołki grafu void deikstra () ( int v [ ROZMIAR ]; // tablica etykiet int temp , i ; int miniindex , min ; for (i = 0 ; i< SIZE ; i ++ ) { d [ i ] = INF ; // tablica ścieżek zainicjowanych do nieskończoności v[i] = 1; ) d [ 0 ] = 0 ; robić( // wykonanie algorytmu indeks = INF ; min = INF ; dla (i = 0 ; i< SIZE ; i ++ ) { if ((v [ i ] == 1 ) && (d [ i ] < min )) { min = d [ i ]; minindex = i ; } } if (minindex != INF ) { for (i = 0 ; i < SIZE ; i ++ ) { if (a [ minindex ][ i ] >0 ) ( temp = min + a [ miniindeks ][ i ]; if (temp< d [ i ]) d [ i ] = temp ; } } v [ minindex ] = 0 ; } } while (minindex < INF ); }
Dany graf ważony skierowany lub nieskierowany z wierzchołkami i krawędziami. Wagi wszystkich krawędzi są nieujemne. Określono jakiś początkowy wierzchołek. Wymagane jest znalezienie długości najkrótszych ścieżek od wierzchołka do wszystkich innych wierzchołków, a także zapewnienie sposobu na wyprowadzenie samych najkrótszych ścieżek.
Ten problem nazywa się problemem najkrótszych ścieżek z jednego źródła.
Algorytm
To opisuje algorytm zaproponowany przez holenderskiego badacza Dijkstra(Dijkstra) w 1959 r.
Uzyskajmy tablicę, w której dla każdego wierzchołka będziemy przechowywać aktualną długość najkrótszej ścieżki od do . Początkowo, i dla wszystkich innych wierzchołków, ta długość jest równa nieskończoności (przy implementacji na komputerze zwykle jako nieskończoność wybierana jest wystarczająco duża liczba, która jest oczywiście większa niż możliwa długość ścieżki):
Dodatkowo dla każdego wierzchołka zapiszemy, czy jest on nadal oznaczony, czy nie, tj. zdobądźmy tablicę logiczną. Początkowo wszystkie wierzchołki są nieoznakowane, tj.
Sam algorytm Dijkstry składa się z iteracje. W kolejnej iteracji wybierany jest wierzchołek z najmniejszą wartością spośród jeszcze nieoznaczonych, tj.:
(Oczywiste jest, że w pierwszej iteracji zostanie wybrany wierzchołek początkowy).
Wybrany w ten sposób wierzchołek jest zaznaczany. Dalej, w obecnej iteracji, z wierzchołka, relaks: sprawdzane są wszystkie krawędzie wychodzące z wierzchołka i dla każdego takiego wierzchołka algorytm próbuje poprawić wartość . Niech długość bieżącej krawędzi będzie , wtedy w postaci kodu relaksacja wygląda tak:
Na tym kończy się bieżąca iteracja, algorytm przechodzi do kolejnej iteracji (ponownie wybierany jest wierzchołek o najmniejszej wartości, od niego wykonywane są relaksacje itd.). W takim przypadku w końcu po iteracjach wszystkie wierzchołki grafu zostaną opatrzone etykietami, a algorytm zakończy swoją pracę. Twierdzi się, że znalezione wartości to wymagane długości najkrótszych ścieżek od do .
Warto zauważyć, że jeśli nie wszystkie wierzchołki grafu są osiągalne z wierzchołka, to wartości dla nich pozostaną nieskończone. Oczywiste jest, że kilka ostatnich iteracji algorytmu po prostu wybierze te wierzchołki, ale te iteracje nie przyniosą żadnej użytecznej pracy (ponieważ nieskończona odległość nie może rozluźnić innych, nawet nieskończonych odległości). Dlatego algorytm może zostać natychmiast zatrzymany, gdy tylko wierzchołek o nieskończonej odległości zostanie wybrany jako wybrany wierzchołek.
Przywrócenie ścieżki. Oczywiście zwykle trzeba znać nie tylko długości najkrótszych ścieżek, ale także same ścieżki. Pokażmy, jak przechowywać informacje wystarczające do późniejszej rekonstrukcji najkrótszej drogi od dowolnego wierzchołka. W tym celu tzw tablica przodków: tablica przechowująca dla każdego wierzchołka numer wierzchołka przedostatniego w najkrótszej ścieżce do wierzchołka. Wykorzystuje to fakt, że jeśli weźmiemy najkrótszą ścieżkę do jakiegoś wierzchołka , a następnie usuniemy ostatni wierzchołek z tej ścieżki, to otrzymamy ścieżkę kończącą się jakimś wierzchołkiem , a ta ścieżka będzie najkrótsza dla wierzchołka . Jeśli więc mamy taką tablicę przodków, to można z niej odtworzyć najkrótszą ścieżkę, po prostu za każdym razem biorąc przodka z bieżącego wierzchołka, aż dojdziemy do wierzchołka początkowego - w ten sposób otrzymamy pożądaną najkrótszą ścieżkę, ale zapisaną w Odwrotna kolejność. Najkrótsza droga na szczyt to:
Pozostaje zrozumieć, jak zbudować tę tablicę przodków. Robi się to jednak bardzo prosto: z każdym udanym relaksem, tj. gdy od wybranego wierzchołka następuje poprawa odległości do jakiegoś wierzchołka , piszemy, że przodkiem wierzchołka jest wierzchołek :
Dowód
Główne oświadczenie, na którym opiera się poprawność algorytmu Dijkstry, wygląda następująco. Stwierdza się, że po zaznaczeniu dowolnego wierzchołka aktualna odległość do niego jest już najkrótsza, a zatem już się nie zmieni.
Dowód wyprodukujemy przez indukcję. Dla pierwszej iteracji jej ważność jest oczywista - dla wierzchołka mamy , czyli długość najkrótszej do niego ścieżki. Teraz niech to twierdzenie utrzyma się dla wszystkich poprzednich iteracji, tj. wszystkie już zaznaczone wierzchołki; udowodnijmy, że nie została naruszona po wykonaniu bieżącej iteracji. Niech będzie wierzchołkiem wybranym w bieżącej iteracji, tj. wierzchołek, który algorytm oznaczy. Udowodnijmy, że tak naprawdę jest równa długości najkrótszej drogi do niej (długość tę oznaczamy przez ).
Rozważ najkrótszą drogę na szczyt. Oczywiste jest, że tę ścieżkę można podzielić na dwie ścieżki: składającą się tylko z oznaczonych wierzchołków (przynajmniej początkowy wierzchołek będzie w tej ścieżce) i pozostałą część ścieżki (może również zawierać zaznaczone wierzchołki, ale zawsze zaczyna się od nieoznaczony). Oznacz pierwszy wierzchołek ścieżki i ostatni wierzchołek ścieżki.
Udowodnijmy najpierw nasze twierdzenie dla wierzchołka , tj. udowodnijmy równość. Jest to jednak prawie oczywiste: w końcu w jednej z poprzednich iteracji wybraliśmy wierzchołek i wykonaliśmy od niego relaksację. Ponieważ (ze względu na sam wybór wierzchołka ) najkrótsza ścieżka do jest równa najkrótszej ścieżce do plus krawędź , to po wykonaniu relaksacji od wartość rzeczywiście zostanie ustawiona na wymaganą wartość.
Ze względu na nieujemność kosztów krawędzi, długość najkrótszej ścieżki (która zgodnie z tym, co właśnie zostało udowodnione, jest równa ) nie przekracza długości najkrótszej ścieżki do wierzchołka . Biorąc pod uwagę, że (w końcu algorytm Dijkstry nie mógł znaleźć krótszej ścieżki niż jest to ogólnie możliwe) w rezultacie otrzymujemy następujące zależności:
Z drugiej strony, ponieważ oba i i są nieoznaczonymi wierzchołkami, ponieważ w bieżącej iteracji wybrano wierzchołek, a nie wierzchołek , otrzymujemy kolejną nierówność:
Z tych dwóch nierówności wnioskujemy równość , a następnie ze znalezionych wcześniej relacji otrzymujemy i:
co było do okazania
Realizacja
Algorytm Dijkstry składa się więc z iteracji, w każdej z których wybierany jest nieoznakowany wierzchołek o najmniejszej wartości, ten wierzchołek jest etykietowany, a następnie wszystkie krawędzie wychodzące z tego wierzchołka są przeglądane i wzdłuż każdej krawędzi podjęta jest próba poprawienia wartość na drugim końcu krawędzi.
Czas działania algorytmu jest sumą:
Przy najprostszej implementacji tych operacji, operacje zostaną poświęcone na znalezienie wierzchołka, a operacje na jednej relaksacji i końcowej asymptotyki algorytm to:
Realizacja:
const int INF = 1000000000 ; int main() ( int n; ... czytaj n ... wektor< vector < pair< int ,int >> > g(n); ... odczyt wykresu... int s = ...; // wierzchołek początkowy wektor< int >d(n, INF), p(n); d[s] = 0; wektor< char >u(n); dla (int i= 0 ; i< n; ++ i) { int v = - 1 ; for (int j= 0 ; j< n; ++ j) if (! u[ j] && (v == - 1 || d[ j] < d[ v] ) ) v = j; if (d[ v] == INF) break ; u[ v] = true ; for (size_t j= 0 ; j< g[ v] .size () ; ++ j) { int to = g[ v] [ j] .first , len = g[ v] [ j] .second ; if (d[ v] + len < d[ to] ) { d[ to] = d[ v] + len; p[ to] = v; } } } }Tutaj wykres jest przechowywany w postaci list sąsiedztwa: dla każdego wierzchołka lista zawiera listę krawędzi emanujących z tego wierzchołka, tj. lista par >, gdzie pierwszym elementem pary jest wierzchołek, do którego prowadzi krawędź, a drugim elementem jest waga krawędzi.
) działa w czasie O(m + n \ln n) i jest asymptotycznie najszybszym znanym algorytmem sekwencyjnym dla tej klasy problemów.
1.2 Matematyczny opis algorytmu
Niech graf G = (V, E) będzie podany z wagami krawędzi f(e) i wyróżnionym wierzchołkiem źródłowym u . Oznacz przez d(v) najkrótszą odległość od źródła u do wierzchołka v .
Niech wszystkie odległości nie przekraczające pewnej liczby r zostały już obliczone, czyli odległości do wierzchołków ze zbioru V_r = \( v \in V \mid d(v) \le r \). Wynajmować
(v, w) \in \arg\min \( d(v) + f(e) \mid v \in V, e = (v, w) \in E \).Następnie d(w) = d(v) + f(e), a v leży na najkrótszej ścieżce od u do w .
Wielkie ilości d^+(w) = d(v) + f(e), gdzie v \in V_r , e = (v, w) \in E , są nazywane szacunkowe odległości i są górnym ograniczeniem dla rzeczywistych odległości: d(w) \le d^+(w) .
Algorytm Dijkstry na każdym kroku znajduje wierzchołek o najmniejszej szacowanej odległości, oznacza go jako odwiedzony i aktualizuje szacowane odległości dla wszystkich punktów końcowych krawędzi z niego wychodzących.
1.3 Rdzeń obliczeniowy algorytmu
Główne obliczenia dotyczą operacji na kolejce priorytetowej:
- wyodrębnienie elementu minimum (delete_min);
- zmniejszyć priorytet elementu (decrease_key).
1.4 Makrostruktura algorytmu
Pseudokod algorytmu:
Dane wejściowe: wykres z wierzchołkami V, krawędzie mi z wagą f(mi); węzeł źródłowy ty. Wyjście: odległości d(v) do każdego wierzchołka v ∈ V z góry ty. Q := Nowy kolejka priorytetowa dla każdego v ∈ V: jeśli v = ty następnie d(v) := 0 w przeciwnym razie d(v) := ∞ Q.wstawić( v, d(v)) podczas gdy Q ≠ ∅: v := Q.delete_min() dla każdego mi = (v, w) ∈ mi: jeśli d(w) > d(v) + f(mi): d(w) := d(v) + f(mi) Q.decrease_key( w, d(w))1.5 Schemat implementacji algorytmu sekwencyjnego
Konkretna implementacja algorytmu Dijkstry zależy od wyboru zastosowanego algorytmu kolejki priorytetowej. W najprostszym przypadku może to być tablica lub lista, wyszukiwanie minimum, w którym wymagane jest przejrzenie wszystkich wierzchołków. Bardziej wydajne jest użycie sterty; najlepiej znane oszacowanie złożoności dotyczy wariantu wykorzystującego stertę Fibonacciego.
Opcja implementacji jest możliwa, gdy wierzchołki są dodawane do kolejki nie na etapie inicjalizacji, ale w czasie pierwszej wizyty.
1.6 Sekwencyjna złożoność algorytmu
Sekwencyjna złożoność algorytmu to O(C_1 m + C_2n) , gdzie
- C_1 - liczba operacji zmniejszania odległości do góry;
- C_2 to liczba operacji do obliczenia minimum.
Oryginalny algorytm Dijkstry używał list jako wewnętrznej struktury danych, dla której C_1 = O(1) , C_2 = O(n) , więc ogólna złożoność wynosiła O(n^2) .
Używając sterty Fibonacciego, minimalny czas obliczeń jest skrócony do C_2 = O(\ln n) , więc całkowita złożoność wynosi O(m + n \ln n) , co jest najlepiej znanym asymptotycznie wynikiem dla tej klasy problemów.
1.7 Wykres informacyjny
Przedstawiono graf algorytmu dla podstawowej implementacji algorytmu Dijkstry na listach lub tablicach.
Rysunek 1. Wykres algorytmu bez wyświetlania danych wejściowych i wyjściowych. n=3. Operacje porównania są zaznaczone na żółto, operacje zmiany etykiet wierzchołków są zaznaczone na zielono, a etykietowanie wierzchołków na niebiesko.
1.8 Zasób równoległości algorytmu
Algorytm Dijkstry pozwala na wydajną równoległość, średni czas działania O(n^(1/3)\ln n) z objętością obliczeniową O(n \ln n + m) .
Pierwsze oszacowanie opiera się na charakterystyce daps, która szacuje liczbę dostępów do pamięci (odczytów i zapisów) wykonanych na sekundę. Ta cecha jest analogiczna do oszacowania flopów w odniesieniu do pracy z pamięcią i jest bardziej oszacowaniem wydajności interakcji pamięci niż oszacowaniem lokalizacji. Służy jednak jako dobre źródło informacji, w tym do porównania z wynikami dla następującej funkcji cvg.
Rysunek 6 pokazuje wartości dapsów dla implementacji popularnych algorytmów, posortowane w kolejności rosnącej (im więcej dapsów, tym ogólnie lepsza wydajność). Widać, że wydajność pamięci jest dość niska. Nie jest to zaskakujące, ponieważ implementacje algorytmów nad grafami prawie zawsze mają niską wydajność ze względu na nieregularność dostępu do danych, którą zaobserwowaliśmy analizując profil dostępu.
Rysunek 6. Porównanie wartości punktacji daps
Druga cecha, cvg, ma na celu zapewnienie bardziej niezależnej od maszyny oceny lokalizacji. Określa, jak często program musi pobierać dane do pamięci podręcznej. W związku z tym im mniejsza wartość cvg, tym rzadziej trzeba to robić, tym lepsza lokalizacja.
Rysunek 7 pokazuje wartości cvg dla tego samego zestawu implementacji, posortowane w kolejności malejącej (im mniejsze cvg, tym ogólnie wyższa lokalizacja). Można zauważyć, że w tym przypadku wartość cvg dobrze koreluje z wynikiem działania i odzwierciedla niską lokalizację, co jest zgodne z ustaleniami jakościowej oceny lokalizacji.
Rysunek 7. Porównanie wartości punktacji cvg
2.3 Możliwe metody i cechy równoległej implementacji algorytmu
2.4 Skalowalność algorytmu i jego implementacja
2.4.1 Skalowalność algorytmu
2.4.2 Skalowalność implementacji algorytmu
Zbadajmy skalowalność równoległej implementacji algorytmu zgodnie z metodologią. Badania przeprowadzono na superkomputerze Łomonosowa należącym do Kompleksu Superkomputerowego Uniwersytetu Moskiewskiego. Zestaw i granice wartości parametrów zmiennych do uruchomienia implementacji algorytmu:
- liczba procesorów z wartościami całkowitymi kwadratowymi;
- wielkość wykresu z krokiem 16000.
Poniższy rysunek przedstawia wykres wydajności wybranej implementacji algorytmu w zależności od zmiennych parametrów uruchamiania.
Rysunek 8. Równoległa implementacja algorytmu. Zmiana wydajności w zależności od liczby procesorów i wielkości regionu.
Ze względu na specyfikę równoległej implementacji algorytmu, ogólna wydajność jest dość niska i rośnie powoli wraz ze wzrostem liczby procesów, a gdy zbliża się do liczby procesów 128, zaczyna spadać. Tłumaczy się to stosowaniem operacji kolektywnych przy każdej iteracji algorytmu oraz faktem, że koszt wymiany komunikacyjnej znacznie wzrasta wraz ze wzrostem liczby wykorzystywanych procesów. Obliczenia na każdym procesie są dość szybkie, dlatego dekompozycja grafu słabo kompensuje wpływ kosztów wymiany komunikacyjnej.
2.5 Charakterystyki dynamiczne i efektywność implementacji algorytmu
Do eksperymentów wykorzystano implementację algorytmu Dijkstry. Wszystkie wyniki uzyskano na superkomputerze Łomonosowa. Wykorzystaliśmy procesory Intel Xeon X5570 o szczytowej wydajności 94 Gflops, a także kompilator Intel 13.1.0. Rysunki pokazują efektywność implementacji algorytmu Dijkstry w 32 procesach.
Rysunek 9. Wykres obciążenia procesora podczas wykonywania algorytmu Dijkstry
Wykres obciążenia procesora pokazuje, że przez prawie cały czas działania programu poziom obciążenia wynosi około 50%. Wskazuje to na jednolite obciążenie procesorów przy użyciu 8 procesów na węzeł obliczeniowy i bez korzystania z funkcji Hyper Threading.
Rysunek 10. Wykres operacji zmiennoprzecinkowych na sekundę podczas wykonywania algorytmu Dijkstry
Rysunek 10 przedstawia wykres operacji zmiennoprzecinkowych na sekundę. Wykres pokazuje ogólnie bardzo słabą wydajność wynoszącą około 250 Kflops w szczycie i średnio około 150 Kflops we wszystkich węzłach. Oznacza to, że prawie wszystkie obliczenia w programie są dokonywane na liczbach całkowitych.
Wykres zapisu do pamięci pokazuje podobny wzór nierówności obliczeniowych, przy czym tylko kilka procesów aktywnie zapisuje w tym samym czasie. Koreluje to z innymi harmonogramami wykonania. Warto zwrócić uwagę na dość małą liczbę dostępów do pamięci. Wskazuje to na dobrą organizację obliczeń i dość wydajną pracę z pamięcią.
Rysunek 15. Wykres szybkości transmisji w sieci Infiniband w bajtach/s przy uruchomionym algorytmie Dijkstry
Na wykresie szybkości przesyłania danych Infiniband występuje dość wysoka szybkość przesyłania danych w bajtach na sekundę. Sugeruje to, że procesy wymieniają między sobą intensywnie i prawdopodobnie raczej niewielkie porcje danych, ponieważ wydajność obliczeniowa jest wysoka. Warto zauważyć, że szybkość transferu różni się między procesami, co wskazuje na nierównowagę obliczeniową.
Rysunek 16. Wykres szybkości transmisji w sieci Infiniband w pakietach/s przy uruchomionym algorytmie Dijkstry
Na wykresie szybkości przesyłania danych w pakietach na sekundę występuje niezwykle wysoka intensywność przesyłania danych. Sugeruje to, że prawdopodobnie procesy wymieniają niezbyt duże ilości danych, ale bardzo intensywnie. Na każdym kroku wykorzystywane są operacje zbiorcze na małych porcjach danych, co wyjaśnia ten obraz. Istnieje również mniejsza nierównowaga między procesami niż widać na wykresach wykorzystania pamięci, obliczeń i transferu danych w bajtach na sekundę. Oznacza to, że procesy wymieniają tę samą liczbę pakietów zgodnie z algorytmem, ale otrzymują różne ilości danych i wykonują nierówne obliczenia.
Rysunek 17. Wykres liczby procesów oczekujących na wejście do etapu liczenia (Loadavg) w trakcie działania algorytmu Dijkstry
Na wykresie liczby procesów oczekujących na wejście w etap zliczania (Loadavg) widać, że wartość tego parametru jest stała przez całą pracę programu i wynosi w przybliżeniu 8. Oznacza to stabilną pracę programu z załadowanym obliczenia przez wszystkie węzły. Wskazuje to na bardzo racjonalne i statyczne ładowanie zasobów sprzętowych przez procesy. I pokazuje dość dobrą wydajność wykonywanej implementacji. Generalnie, zgodnie z systemem monitoringu programu, można stwierdzić, że program działał dość sprawnie i stabilnie. Użycie pamięci jest bardzo intensywne, a użycie mediów komunikacyjnych bardzo intensywne, a transfer danych nie jest wysoki. Wskazuje to na dokładną naturę opóźnienia środowiska komunikacyjnego algorytmicznej części programu. Niska wydajność wydaje się być związana z dość dużą liczbą transferów na proces i intensywną wymianą wiadomości.