Złożoność czasu Dijkstry

„Algorytm Dijkstry szuka najkrótszej ścieżki między dowolnymi dwoma węzłami na wykresie. Węzeł jest również nazywany wierzchołkiem w wykresie. Gałąź na wykresie jest również nazywana krawędzią. Dla uproszczenia program w tym artykule będzie szukał najkrótszej ścieżki między źródłem wierzchołkiem a jednym docelowym wierzchołkiem."

Rozważ następujące miasta: A, B, C, D, E i F połączone drogami:

Te miasta są połączone drogami (które można założyć, że są proste). Długość drogi od miasta A do miasta B wynosi 4 jednostki; nie jest narysowany do skali. Długość drogi od miasta A do miasta C wynosi 5 jednostek; nie jest narysowany do skali. Długość od miasta B do miasta E to 11 jednostek, a nie pociągnięte do skali. Drogi między innymi miastami są podobnie wskazane.

Miasta: A, B, C, D, E i F to wierzchołki wykresu. Drogi są krawędzią wykresu. Jednak wykres ten będzie reprezentowany w matematycznej strukturze danych, inaczej niż jego układ geograficzny.

Algorytm Dijkstry można użyć do znalezienia najkrótszej ścieżki między źródłowym wierzchołkiem (powiedz a) a dowolnym innym wierzchołkiem. Aby uzyskać dalszą prostotę, ten artykuł będzie miał na celu poszukiwanie najkrótszej ścieżki od A do E.

Istnieją różne ścieżki od A do E, z różnymi długościami, w następujący sposób:

A-B-D-F: 4 + 9 + 2 = 15
A-B-E-F: 4 + 7 + 6 = 17
A-B-C-E-F: 4 + 11 + 3 + 6 = 24
A-B-C-E-D-F: 4 + 11 + 3 + 13 + 2 = 33
A-B-D-E-F: 4 + 9 + 13 + 6 = 32
A-B-E-D-F: 4 + 7 + 13 + 2 = 26
A-C-E-F: 5 + 3 + 6 = 14
A-C-B-D-F: 5 + 11 + 9 + 2 = 27
A-C-B-E-F: 5 + 11 + 7 + 6 = 29
A-C-B-E-F: 5 + 11 + 7 + 6 = 29
A-C-E-D-F: 5 + 3 + 13 + 2 = 14
A-C-B-E-D-F: 5 + 11 + 7 + 13 + 2 = 38

Z tej listy najkrótszą ścieżką jest A-C-E-F, z całkowitą długością 14 jednostek.

Głównym celem tego artykułu jest znalezienie algorytmu Dijkstra w czasie bieżącego, aby uzyskać najkrótszą ścieżkę od A do E. Czas nie będzie dany w ciągu kilku sekund lub minut. Jest to względny całkowity czas wykonania, zwany złożonością czasu, zostanie podany. Dostarczane jest również kodowanie C ++.

Wykres do użycia

Złożoność czasu (względny czas działania) zależy głównie od rodzaju wykresu matematycznego używanego do przedstawienia układu geograficznego. Zależy również od algorytmu (inny rodzaj algorytmu) stosowany do sortowania sąsiednich wierzchołków każdego wierzchołka w ogólnym algorytmie (algorytm Dijkstry). Sortowanie sąsiednich wierzchołków nie jest adresowane w tym artykule.

Wykres matematyczny wybrany dla tego artykułu nazywa się macierzą przylegania. To jest:

Nagłówki rzędowe to nazwy miast od A do F. Nagłówki kolumnowe to te same nazwy miast od A do F. Każdy wpis jest długością drogi z jednego miasta do drugiego. Długość drogi z jednego miasta do siebie wynosi zero. Długość drogi z jednego miasta do drugiego, po pominięciu jednego lub więcej miast, również wynosi zero. Rozważane są tylko bezpośrednie drogi. Każdy wpis znajduje się, najpierw w wierszu, a następnie według kolumny. Ponownie, każde wejście jest długością jednej drogi, bez pomijania miasta, a nie do samego miasta. Ta macierz jest matematyczną reprezentacją sieci geograficznej podanej powyżej.

Tak więc macierz składa się z krawędzi, z nagłówkami wiersza i kolumnami tych samych wierzchołków. Matryca to główna struktura potrzebna w programie. W tym podstawowym programie są używane dwa inne wektory (tablice).

Algorytm Dijkstry

Algorytm Dijkstry szuka najkrótszej ścieżki między dowolnymi dwoma wierzchołkami na wykresie (sieć). Powyższa matryca to wykres, który odpowiada powyższej sieci geograficznej. Dla uproszczenia program w tym artykule będzie szukał najkrótszej ścieżki między źródłem wierzchołkiem a jednym docelowym wierzchołkiem. Dokładnie program będzie szukał najkrótszej ścieżki od źródła wierzchołka, a, do docelowego wierzchołka, f.

Algorytm, tak samo istotny dla tego zadania, jest następujący:

- Wszystkie wierzchołki są oznaczone jako niewiarygodne. W tym momencie tworzone jest zestaw wszystkich niewidocznych wierzchołków.

- Przypisz wstępną wartość długości ścieżki do wszystkich wierzchołków: Długość ścieżki od źródła do źródła przypisuje się wartość zero; Długość ścieżki od źródła do dowolnego innego wierzchołka jest przypisana jednej wartości nieskończoności, i.mi., wartość, która jest wyższa niż najwyższa możliwa ścieżka, na wykresie. Wartość każdego wierzchołka zostałaby zmieniona co najmniej raz, z wysokiej wartości na niższą wartość, ponieważ algorytm trwa. Możliwe wierzchołki dla kompletnej najkrótszej ścieżki zostaną skoncentrowane, zaczynając od źródła wierzchołka (a). Wierzchołek z fokusem nazywa się bieżącym wierzchołkiem. Obecny wierzchołek ma sąsiadów, lepiej wizualizowane z rzeczywistej sieci (układ geograficzny) powyżej.

- Jest obecny wierzchołek i odwiedzony wierzchołek. W rzeczywistości w łańcuchu byłoby więcej niż jeden wierzchołek, ponieważ algorytm trwa. Wszystkie poprzednie rozważane wierzchołki znajdują się na najkrótszej kompletnej ścieżce, która jest rozwijana, zaczynając od źródła. Ścieżka ostatniego odwiedzonego wierzchołka jest znana (powinna być znana). Wierzchołek jest zadeklarowany odwiedzany po potwierdzeniu jego długości ścieżki. Odwiedzony wierzchołek daje jak dotąd długość ścieżki ze źródła, ponieważ algorytm jest w toku. Niewidziani sąsiedzi obecnego wierzchołka, z wyjątkiem jego bezpośredniego poprzedniego odwiedzanego sąsiada, mają wartości niepewne (długości ścieżki ze źródła), z których niektóre mogą być nadal nieskończoności (bardzo wysoka wartość). Dla każdego niewidocznego sąsiada i prądu wierzchołka obliczana jest nowa wstępna długość ścieżki w następujący sposób: długość ścieżki wcześniej odwiedzonego wierzchołka, a także długość krawędzi do prądu wierzchołka, a także długość krawędzi od prądu do wierzchołka do niewidziany sąsiad. Jeśli ten wynik jest mniejszy niż to, co tam było, jako wstępna długość ścieżki od źródła do niewidocznego sąsiada bieżącego wierzchołka, wówczas ta obliczona wartość staje się nową wartością niepewną dla sąsiada bieżącego wierzchołka. Oznacza to, że nowa wartość ścieżki wstępnej dla niewidomowanego wierzchołka jest obliczana przez bieżący wierzchołek z wcześniej odwiedzonego wierzchołka.

- Może być więcej niż jeden obecny wierzchołki. Gdy wszystkie sąsiedzi każdego bieżącego wierzchołka zostały dostępne i otrzymali nowe odpowiednie wstępne długości ścieżki, bieżący wierzchołek o najmniejszej długości ścieżki od źródła (najmniejsza wartość) jest uważany. Ponieważ miał najmniejszą wartość, jego najmniejsza wartość jest potwierdzona jako najkrótsza do tej pory długość częściowej ścieżki. Wcześniej odwiedzony wierzchołek jest usuwany z niezapomnianego zestawu wierzchołków. Odwiedzony wierzchołek nigdy więcej nie zostanie sprawdzony. Wszelkie wizyty po miałyby większą długość ścieżki.

- Poprzednie dwa kroki są powtarzane w kolejności dla każdego następnego bieżącego wierzchołka, który staje się odwiedzonym wierzchołkiem. Powtórzenie to trwa do momentu osiągnięcia docelowego wierzchołka. Docelowym wierzchołkiem może być dowolny wierzchołek po źródłach wierzchołku. Jednak dla uproszczenia ostatni wierzchołek, F powyższej sieci, został wybrany jako wierzchołek docelowy dla tego artykułu.

- W miarę postępu algorytmu każdy rodzic (wcześniej odwiedzony) wierzchołek i każde dziecko (następne odwiedzone) wierzchołek, najkrótszej ścieżki, należy zarejestrować w przypadku najkrótszej ścieżki, według wierzchołków, a także najkrótszej ścieżki po długości ( spytany o). Po osiągnięciu i odwiedzeniu docelowego wierzchołka, pełnej najkrótszej ścieżki można prześledzić do tyłu, jeśli potrzebna jest ścieżka według wierzchołków. Jeśli chodzi o długość ścieżki, obliczono ją w miarę postępu algorytmu.

Ilustracja algorytmu Dijkstra

Powyższa droga

Sieć służy do zilustrowania algorytmu Dijkstry. Jest ponownie przełączany poniżej dla łatwego odniesienia.

Zaczyna się u źródła „a” o długości ścieżki zerowej. „A” jest uważane za odwiedzane i usunięte z listy niezapomnianej (zestaw). „A” jest wysyłane do odwiedzonej listy na wypadek, gdyby wymagana będzie ścieżka według wierzchołków.

Ścieżka od A do B to:

A-B = 4
A-C-B = 5 + 11 = 16

Między 4–16 i nieskończonością (która tam była), 4 to najmniej. Tak więc B otrzymuje wstępną wartość 4 jako długość ścieżki.

Ścieżka od A do C to:

A-C = 5
A-B-C = 4 + 11 = 15

Między 5–15 i nieskończonością (która tam była), 5 jest najmniej. Tak więc C otrzymuje wartość wstępną 5 jako długość ścieżki.

B i C byli niewidzianymi sąsiadami. Obecnie każdy ma wstępną długość ścieżki. Między B i C należy wybrać wierzchołek przyczyniający się do ostatecznej ogólnej ścieżki. B i C mają również sąsiadów.

Niewidziani sąsiedzi B są D, E i C, z wstępnymi nieskończonymi długościami. Nieprzestrzegani sąsiedzi C są B i E z niepewnymi nieskończonymi długościami. Sąsiad ma jedną bezpośrednią przewagę od danego wierzchołka.

Długość ścieżki obliczonej od A do D, do B to:

A-B-D = 4 + 9 = 13

Długość ścieżki obliczonej od A do E, do B to:

A-B-E = 4 + 7 = 11

Długość ścieżki obliczonej od A do C, do B wynosi:

A-B-C = 4 + 11 = 15

Są to długości ścieżki przez B do sąsiadów B, od odwiedzonego wierzchołka „A”. Należy również określić wstępne długości ścieżki przez C.

Długość ścieżki obliczonej od A do B, do C to:

A-C-B = 5 + 11 = 16

Długość ścieżki obliczonej od A do E do C to:

A-C-E = 5 + 3 = 8

Są to długości ścieżki przez C do sąsiadów C, od odwiedzonego wierzchołka „A”.

Wszystkie dotychczasowe obliczone długości częściowej ścieżki to:

A-B-D = 4 + 9 = 13
A-B-E = 4 + 7 = 11
A-B-C = 4 + 11 = 15
A-C-B = 5 + 11 = 16
A-C-E = 5 + 3 = 8

Najkrótsze z tych częściowej ścieżki to:

A-C-E = 5 + 3 = 8

Więc wierzchołek, c, jest wybierany na drogę do przodu. To jest następny odwiedzony wierzchołek. Każda możliwa ścieżka przez B jest porzucona. C jest następnie uważane za odwiedzane. Wierzchołek C jest usuwany z listy niezapomnianej. C jest wysyłany na listę odwiedzoną (po A).

C powinien mieć nieznanych sąsiadów o niepewnych długościach ścieżki. W takim przypadku jest to B i E. B ma sąsiadów z nieskończonymi długościami ścieżki, które są D i E. E ma sąsiadów z nieskończonymi długościami ścieżki, które są D i F. Aby wybrać następny odwiedzony węzeł, należy obliczyć wstępne długości części części od C do B i E. Obliczenia to:

A-C-B-D = 5 + 11 + 9
= 16 + 9 = 25
A-C-B-E = 5 + 11 + 7
= 16 + 7 = 23
A-C-E-D = 5 + 3 + 13
= 8 + 13 = 21
A-C-E-F = 5 + 3 + 6
= 8 + 6 = 14

Najkrótsze dla tych części części to:

A-C-E-F = 8 + 6 = 14

W tym momencie E jest drogą do przodu. To jest następny odwiedzony wierzchołek. Każda możliwa ścieżka przez D jest porzucona. E jest usuwane z listy niezapomnianej i dodawane do listy odwiedzonej (po C).

E ma niezbadanych sąsiadów o wstępnych długości ścieżki. W tym przypadku jest to D i F. Gdyby F miał niewidzianych sąsiadów, ich niepewna ścieżka od „A”, źródłem, powinna być nieskończoność. Teraz długość od F do nic wynosi 0. Aby wybrać następny odwiedzony węzeł (wierzchołek), należy obliczyć wstępne długości części części od E do D i E do F. Obliczenia to:

A-C-E-D-F = 5 + 3 + 13 + 2
= 8 + 15 = 23
A-C-E-F- = 5 + 3 + 6 + 0
= 14 + 0 = 14

Najkrótsze z tych częściowej ścieżki to:

A-C-E-F- = 14

W tym momencie F jest drogą do przodu. Jest uważany za odwiedzony. F jest usuwane z listy niezapomnianej i dodaje się do odwiedzonej listy (po E).

F jest celem. I tak, najkrótsza długość ścieżki od źródła, a, do miejsca docelowego, f, wynosi 14. Wierzchołki i ich zamówienie na liście odwiedzonej powinny być A-C-E-F. To jest najkrótsza ścieżka do przodu według wierzchołków. Aby uzyskać odwrotną najkrótszą ścieżkę według wierzchołków, przeczytaj listę wstecz.

Kodowanie C ++

Wykres

Wykres dla sieci to dwuwymiarowa tablica. To jest:

int g [v] [v] = 0,4,5,0,0,0,
4,0,11,9,7,0,
5,11,0,0,3,0,
0,9,0,0,13,2,
0,7,3,13,0,6,
0,0,0,2,6,0;

Należy go zakodować w głównej funkcji C ++. Każdy wpis jest długością krawędzi od jednego wierzchołka, odczytu do wierszy, do następnego wierzchołka, odczytu po kolumnach. Taka wartość nie dotyczy więcej niż jednej pary wierzchołków.

Wierzchołki jako liczby

Dla wygody wierzchołki zostaną zidentyfikowane przez liczby, za pomocą kodowania ASCII, w następujący sposób:

A to 65
B ma 66
C to 67
D to 68
E to 69
F ma 70
A to 0 + 65 = 65
B wynosi 1 + 65 = 65
C to 2 + 65 = 65
D wynosi 3 + 65 = 65
E to 4 + 65 = 65
F ma 5 + 65 = 65

Wartości kodujące dla A, B, C, D, E i F są następujące:

A = 0
B = 1
C = 2
D = 3
E = 4
F = 5

65 zostanie dodane do każdej z tych liczb, aby uzyskać odpowiedni numer ASCII, z którego zostanie uzyskana odpowiednia litera.

Początek programu

Początek programu to:

#włączać
#włączać
za pomocą przestrzeni nazw Std;
int int_max = +2'147'483'647; //nieskończoność
#definicja V 6 // Numer wierzchołka w g
int KrewestLength = int_max;
wektor niewidoczny = 0, 1, 2, 3, 4, 5;
VectorVisited;

Wartość nieskończoności wybranej przez programistę to 2147483647. Liczba wierzchołków, v (w wieloletniach), jest zdefiniowana (przypisana) jako 6. Elementy niewidomowanego wektora (tablica) to A, B, C, D, E i F, AS 0, 1, 2, 3, 4, 5, odpowiadające numerom kodów ASCII 65, 66, 67, 68, 69, 70. Ta kolejność w tym przypadku niekoniecznie jest z góry określoną, posortowaną kolejnością. Odwiedzone wierzchołki zostaną wepchnięte do odwiedzonego wektora w kolejności odkrytych przez algorytm, poczynając od źródłowego wierzchołka.

Funkcja getneighbors ()

Ta funkcja uzyskuje wszystkich sąsiadów przed wierzchołkiem, zaczynając od tuż po wcześniej odwiedzonym powiązanym wierzchołku. Kod funkcji to:

vectorgetneighbors (int wykres [v] [v], int vindx, int prevvisitedIndx)
VectorNeighbors;
dla (int j = prevvisitedindx+1; jif (wykres [vindx] [j] != 0)
sąsiedzi.push_back (j);

powrót sąsiadów;

Funkcja Dijkstra ()

Po uwzględnieniu programu źródłowego (Vertex) funkcja Dijkstra () wchodzi w działanie rekurencyjnie, dopóki nie zostanie rozważony indeks docelowy (Vertex). Kod funkcji to:

void Dijkstra (int wykres [v] [v], int visetedIdx, int visitLength)
int visitIdIndx = ViseIdIdx;
int newVisitedIndx = v;
int minLength = int_max;
int odwiedzana długość;
int nentledngth1 = 0;
VectorvisitedNbs = getneighbors (wykres, wizytaDinDX, ViseIdIdx);
dla (int i = 0; iTentLength1 = VisitLength + Graph [ViseIdIdx] [VisetedNbs [i]];
vectorCurrentnbs = getneighbors (wykres, odwiedzoneNB [i], viseatIdx);
if (currentnbs.rozmiar() != 0)
for (int j = 0; j int namiot długość2 = gabet namioth1 + [odwiedziłNBS [i]] [currentnbs [j]];
if (namiot długość2 VisitedLength = namiot długość1; // potwierdzone, jeśli skończy się najmniej
newVisitedIndx = visetedNbs [i];



w przeciwnym razie
VisitedLength = namiot długość1; //potwierdzony
newVisitedIndx = visetedNbs [i];


VisitedIndx = newVisitedIndx;
niewidziane [wizytaDinDx] = -1;
odwiedzone.push_back (wizytaDinDx);
najkrótsza długość = odwiedzana długość;
if (odwiedzonedx< V -1)
Dijkstra (wykres, odwiedzonyDinx, wizyta długość);

Funkcja startDiJkstra ()

Algorytm Dijkstry zaczyna się od tej funkcji, aby obsłużyć sytuację kodu źródłowego. Kod funkcji to:

void startDiJkstra (int wykres [v] [v], int srcvidx)
int viseedIndx = srcvidx;
niewidziane [wizytaDinDx] = -1;
odwiedzone.push_back (wizytaDinDx);
int odwiedzana długość = 0;
Dijkstra (wykres, odwiedzonyDinx, wizyta długość);

Powyższe segmenty kodu można składać w kolejności podanej w celu utworzenia programu.

Główna funkcja C ++

Odpowiednia główna funkcja C ++ to:

int main (int argc, char ** argv)

int g [v] [v] = 0,4,5,0,0,0,
4,0,11,9,7,0,
5,11,0,0,3,0,
0,9,0,0,13,2,
0,7,3,13,0,6,
0,0,0,2,6,0;
int Sourcevertex = 0;
startDiJkstra (G, Sourcevertex);
Cout<dla (int i = 0; iCout<< (char)(visited[i] + 65) << ";
Cout<powrót 0;

Wniosek

Złożoność czasu to względny czas działania. Zakładając, że sortowanie wierzchołków (sąsiadów) jest dobre, powyższy program ma następną złożoność:

O ((| e | + | v |) log | v |)

gdzie | e | to liczba krawędzi, | v | to liczba wierzchołków, a dziennik to dziennik₂. Big-O z nawiasami () jest sposobem na wskazanie, że wyrażenie w nawiasach jest złożonością czasu (względny czas działania).

Najgorsze złożoność czasu dla algorytmu Dijkstry jest: O (| V |²)
[/cc]