Metoda Daekstra znajdująca najkrótszą ścieżkę. Wykresy. Znalezienie najkrótszej odległości między dwoma wierzchołkami za pomocą algorytmu deiquistra. Schemat algorytmu sekwencyjnego

Algorytm Daekstra jest algorytmem na wykresach, co znajduje najkrótszą ścieżkę między dwoma wierzchołkami na wykresie z nieodegatywnymi długościami łuku. Często jest również zadaniem obliczania najkrótszej ścieżki z tego wierzchołka do wszystkich innych. Algorytm jest szeroko stosowany w programowaniu, na przykład, jest używany przez protokoły routingu.

Opis

Wejście algorytmu otrzymuje ważony wykres zorientowany za pomocą łuku nie ujemnego wagi. Wyjście jest zestawem najkrótszych ścieżek z tego wierzchołka do innych.

Na początku zakłada się, że odległość dla początkowego wierzchołka wynosi zero, a odległości dla wszystkich innych są rozumiane nieskończone. Tablica flag oznaczających, czy górna jest minęła, wypełniona zerami. Następnie, na każdym etapie cyklu, góra o minimalnej odległości do początkowej i flagi równej zero jest wyszukiwane. Za to, że flaga jest zainstalowana, a wszystkie sąsiednie wierzchołki są sprawdzane. Jeśli poprzednia odległość od źródła wierzchołka jest wcześniej sprawdzana niż ilość odległości do prądu wierzchołka i długość żebra z niego do sprawdzonego wierzchołka, a następnie odległość do testowanego wierzchołka równa się odległości do prądu + krawędzi z prądu do aktualnie sprawdzonego. Cykl jest zakończony, gdy flagi wszystkich wierzchołków stają się równe 1, lub gdy odległość do wszystkich wierzchołków z flagą 0 jest nieskończona. Ostatni przypadek jest wtedy i tylko wtedy, gdy liczba jest nietolerancyjna.

Algorytm Daekstra. w pseudokodzie.

Wejście: Z : Macierzy z matrycy dziennika ARC Real - Count; S jest wierzchołkiem, z którego najkrótsza ścieżka i T jest wierzchołkiem, którego szukasz.

Wyjście: v\u003e macierz rzeczywistego; i n: macierz 0..r. Jeśli top v. Leży w najkrótszej ścieżce z s. do t, że TELEWIZJA]- Długość najkrótszej ścieżki s. do y; H [y] - Top, bezpośrednio poprzedzający w. W najkrótszej ścieżce.

H jest tablicą, w której wierzchołek N odpowiada wierzchołku M, poprzednim w drodze do N z S.

T jest tablicą, w której wierzchołek n odpowiada odległości od niego do S.

X jest tablicą, w której wierzchołek n odpowiada 1, jeśli ścieżka jest znana, a 0, jeśli nie.

inicjalizacja tablic:

dla v. od 1 do. r. zrobić.

T [v.]: = ∞ (Najkrótsza ścieżka jest nieznana)

X [V]: \u003d 0 (wszystkie wierzchołki nie są zaznaczone)

H [S]: \u003d 0 ( s. nic poprzedzającego)

T [S]: \u003d 0 (najkrótsza ścieżka ma długość 0 ...)

X [S]: \u003d 1 (... i jest znany) v. : = s. (Aktualny wierzchołek)

M: (aktualizuj znaki)

dla i ∈. G ( i) zrobić.

gdyby X [i] = 0 & T [i]> TELEWIZJA] + DO. Następnie.

T [i]: = TELEWIZJA] + DO. (krótsza ścieżka s. w i przez v. }

H [u]:= v. (pamiętam)

m.: = ∞

v. : = 0

(Wyszukaj koniec najkrótszej ścieżki)

dla i od 1 do. p. zrobić.

gdyby X [U] = 0 & T [U]< t. Następnie.

v:= u.;

m:= T [u] (Top v. kończy najkrótszą ścieżkę s.

gdyby v. = 0 Następnie.

zatrzymaj (brak ścieżki s. w t.) Koniec IF.

gdyby v.= t. Następnie.

zatrzymaj się (najkrótsza ścieżka s. w t.) Koniec IF.

X [V]: \u003d 1 (najkrótsza ścieżka z s. w v. ) Iść do. M.

Usprawiedliwienie

Aby udowodnić poprawność algorytmu Daekstra, wystarczy zauważyć, że przy każdym wykonaniu korpusu cyklu, który rozpoczyna etykietę M, jak v.używany jest wierzchołek, do którego znana jest najkrótsza ścieżka z góry. s.Innymi słowy, jeśli X [V] \u003d 1, a następnie T [V] \u003d D (S, V) , I wszystkie wierzchołki na ścieżce (S, V), określone przez NN, mają tę samą nieruchomość, czyli

Vu t [i] \u003d 1 \u003d\u003e t [i] \u003d d (s, u) & t] \u003d 1.

Naprawdę (przez indukcję), pierwszy raz v. Vertex S jest używany, do którego pusta jest pusta ścieżka i ma długość 0 (nie pustych ścieżek nie może być krótszy, ponieważ długość łuków nie jest negatywna). Niech t [u] \u003d d (s, u) dla wszystkich wcześniej zaznaczonych wierzchołków i. Rozważ nowo oznaczony wierzchołek v.który jest wybrany z warunku T [V] \u003d min t [i]. Zauważ, że jeśli sposób jest znany przez oznaczone wierzchołki, znane jest również z najkrótszej ścieżki. Załóżmy (inaczej), że t [v]\u003e d (s, v), to znaczy ścieżka prowadziła s.w v,nie jest najkrótszy. Następnie powinno być nieodwracalne wierzchołki na tej ścieżce. Rozważ pierwszy wierzchołek w.na tej ścieżce tak, że T [W] = 0. IIM: T [W] = d (s, w) ⩽d (s\u003e v)< Т[v],что противоречит выбору вершины u.

Tymczasowa trudność

Złożoność algorytmu DaEkstra zależy od sposobu ustalenia nie odwiedzanego przez górną o minimalnej odległości do początkowej metody przechowywania wielu nieobrobionych wierzchołków i metod aktualizacji znaczników. Niech n będzie liczbą wierzchołków, a przez m - liczba krawędzi w kolumnie. Następnie, w najprostszym przypadku, gdy wszystkie ustawione wierzchołki są przeglądane w celu wyszukiwania wierzchołków z minimalną odległością do początkowego wierzchołka, a tablica służy do przechowywania odległości, czas pracy algorytmu - O (N2). Główny cykl jest wykonywany o N razy, w każdym z nich, minimum spędza się na operacjach N. Liczba operacji spędza na cyklach wzdłuż sąsiadów każdej wizyty wierzchołka, liczba robisla M (ponieważ każda krawędź znajduje się w tych cyklach płynnie dwukrotnie i wymaga stałej liczby operacji). W ten sposób ogólny czas pracy algorytmu O (N2 + M), ale ponieważ M jest mniejszy niż N (N-1), ostatecznie okazuje się (N2).

W przypadku wyrównanych wykresów (to znaczy takie, dla których M jest znacznie mniej niż N2)) Niekryty wierzchołki mogą być przechowywane w stercie binarną i jako klucz do używania odległości. Ponieważ cykl jest wykonywany o n czasie, a liczba relaksu (zmiany etykiet) nie jest więcej niż m, czas działania takiej implementacji - O (Nlogn + Mlogn)

Przykład

Obliczanie odległości z wierzchołka 1 do przechodzących wierzchołków:

Przed każdym obszarem miasta (jeśli możesz poruszać się tylko na drogach).

Opcja 2. Istnieją kilka lotów między miastami na świecie, dla każdego słynnego kosztu. Koszt lotu z A do B może nie być równy kosztowi lotu z B do A. Znajdź trasę minimalnego kosztu (ewentualnie z transferami) z Kopenhaga do Barnaul.

Formalna definicja

Przykład

Rozważ realizację algorytmu na przykładzie wykresu pokazanego na rysunku.

Niech musi znaleźć najkrótszą odległość od pierwszego wierzchołka do wszystkich innych.

Wdrożenie w językach programowania

Wydajność w języku C (Si)

#Define rozmiar 6 #define INF 1000000000 INT A [rozmiar] [rozmiar] \u003d ((INF, 5, INF, INF, INF, INF), (1, 2, 3, 4, 5, 6), // ścieżki matrycy (1, 2, 3, 4, 5, 6), (1, 2, 3, 4, 5, 6), // poziome indeksy z punktu { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // pionowy do punktu, wartość - waga Int d [rozmiar]; // Tablica znalezionych najkrótszych ścieżek, indeksy - wierzchołki wykresu void deikstra () (int V [rozmiar]; // tablica etykiet int Temp, I; Int minindeks, min; dla (i \u003d 0; ja< SIZE ; i ++ ) { d [ i ] = INF ; // Grafika ścieżek jest inicjowana nieskończoność v [I] \u003d 1; ) D [0] \u003d 0; zrobić ( // Wykonanie algorytmu minindeks \u003d inf; Min \u003d Inf; dla (i \u003d 0; ja< 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 \u003d MIN + A [MININDEX] [I]; IF (TEMP< d [ i ]) d [ i ] = temp ; } } v [ minindex ] = 0 ; } } while (minindex < INF ); }

najkrótsza droga Dziś jest to ważne zadanie i jest używany niemal wszędzie, od znalezienia optymalnej trasy między dwoma obiektami na ziemi (na przykład najkrótszej ścieżki z domu na uniwersytet), w systemach autopilot, aby znaleźć optymalną trasę podczas transportu, Pakiet informacyjny w sieciach i T.P.

Najkrótsza ścieżka jest uważana za pomocą pewnego obiektu matematycznego o nazwie wykres. Szukaj najkrótsza droga Jest prowadzony między dwoma określonymi wierzchołkami na wykresie. Rezultatem jest ścieżka, która jest sekwencją wierzchołków i żeber, incydent do dwóch sąsiednich wierzchołków i jej długości.

Rozważ trzy najwięcej skuteczny algorytm Nośny najkrótsza droga:

• algorytm Daekstra.;
• Algorytm Floyda;
• overnorn algorytmy.

Te algorytmy są łatwo wykonywane z małą liczbą wierzchołków na wykresie. Ze wzrostem ich liczby zadań wyszukiwania najkrótsza droga Kompletny.

Algorytm Daekstra.

Ten algorytm jest algorytmem na wykresach, który został wymyślony przez Holandia Naukowiec E. DyAKStroy w 1959 roku. Algorytm znajduje najkrótszą odległość od jednego z wierzchołków wykresu do wszystkich innych i działa tylko na wykresy bez żeber o negatywnej masy.

Każdy wierzchołek przypisuje się wagi - jest to waga ścieżki z początkowego wierzchołka do tego. Również każdy wierzchołek może być podświetlony. Jeśli wierzchołek jest podświetlony, ścieżka z niego do początkowego wierzchołka najkrótsza, jeśli nie, a następnie tymczasowa. Nadchodząc przez wykres, algorytm uważa drogę dla każdego wierzchołka, a jeśli okaże się najkrótszy, podkreśla górę. Waga tego wierzchołka jest ciężarem ścieżki. Dla wszystkich sąsiadów tego wierzchołka algorytm oblicza również wagę, bez żadnych okoliczności w żadnych okolicznościach. Algorytm kończy swoją pracę, osiągając ostateczny wierzchołek i ważenie najkrótsza droga Waga końcowego wierzchołka staje się.

Algorytm Daekstra.

Krok 1. Do wszystkich szczytów, z wyjątkiem pierwszego, waga przypisana jest równa nieskończoność, a pierwszy wierzchołek wynosi 0.

Krok 2. Wszystkie wierzchołki nie są podświetlone.

Krok 3. Pierwszy wierzchołek jest zadeklarowany prąd.

Krok 4. Waga wszystkich niezamieszkanych wierzchołków jest tłumaczona przez wzór: Masa niezbadanego wierzchołka jest minimalną liczbą starej masy tego wierzchołka, ilość masy prądu wierzchołka i masy krawędzi łączącej Aktualny wierzchołek z nierozróżnianym.

Krok 5. Wśród niezbędnych pików jest góra z minimalną wagą. Jeśli nie zostanie znalezione, to znaczy waga wszystkich wierzchołków jest równa nieskończoności, trasa nie istnieje. W konsekwencji wyjście. W przeciwnym razie prąd jest wynikiem wynikowym. Jest przydzielony.

Krok 6. Jeśli bieżący wierzchołek okazuje się być ostatecznym, pojawia się ścieżka, a jego waga jest masą końcowego wierzchołka.

Krok 7. Przejdź do Krok 4.

W realizacji oprogramowania algorytm Daekstra. Będziemy skonstruować zestaw wierzchołków S, dla których najkrótsze ścieżki z początkowego wierzchołka są już znane. Przy każdym kroku do set s dodaje się ten sam wierzchołek, odległość od początkowego wierzchołka jest mniejsza niż dla innych pozostałych wierzchołków. W tym przypadku użyjemy tablicy D, w której długości są rejestrowane najkrótsze ścieżki Dla każdego wierzchołka. Gdy set S zawiera wszystkie wierzchołki wykresu, a następnie tablarek D zawiera długości najkrótsze ścieżki Z początkowego wierzchołka do każdego wierzchołka.

Oprócz określonych tablic, użyjemy matrycy C C, gdzie element C jest długości krawędzi (I, J), jeśli nie ma żebra, to jego długość jest oparta na równej nieskończonej, to znaczy więcej niż jakakolwiek rzeczywista długość żebra. Właściwie matryca C jest matryca żeglarska.w którym wszystkie elementy zerowe są zastępowane nieskończonością.

Aby określić samą

5.4.3. Wyzwanie najkrótszej ścieżki i algorytmu Daekster swojej decyzji

Pozwól, aby Orgraf SOL.(V., MI.), z których każdy łuk jest umieszczony zgodnie z numerem
nazywa Łuk długo.

Definicja. Lena. Ścieżka nazywana jest sumą długości łuku, które tworzą tę ścieżkę. Zadanie najkrótszej ścieżkistawia tak.

Opcja 1. Znajdź długości najkrótszych ścieżek (sposoby minimalnej długości) i same ścieżki ze stałego wierzchołka s. do wszystkich innych wierzchołków wykresu.

Opcja 2. Znajdź długości najkrótszych ścieżek i samych ścieżki między wszystkimi parami wierzchołków tego wykresu.

Jeśli w kolumnie znajdują się negatywne łuki, zadanie może nie mieć rozwiązań (stracą znaczenie). Wynika to z faktu, że kontur negatywnej długości może być obecny w kolumnie. Obwód obwodów ujemnych oznacza, że \u200b\u200bdługość ścieżki może być równa
. A jeśli nie ma obwodów negatywnych, istnieją najkrótsze ścieżki, a dowolna najkrótsza ścieżka jest prostym łańcuchem.

Należy pamiętać, że jeśli najkrótsza ścieżka istnieje, to każdy z nich jest, jest to również najkrótsza droga między odpowiednimi wierzchołkami.

Algorytm Daekstra rozwiązywanie problemu najkrótszej ścieżki.

Algorytm pracuje z łukami o dodatniej długości i definiuje najkrótsze ścieżki ze stałego wierzchołka s. do wszystkich innych wierzchołków wykresu. Oznacz te wierzchołki v. 1 , v. 2 ,…, v. n. .

Definicja. Zadzwońmy na górę u. leżąc bliżej góry s.niż top v.Jeśli długość najkrótszej ścieżki s. przed u. mniej niż długość najkrótszej ścieżki s. przed v.. Powiemy, że szczyty u. i v. wyrównany Z góry s.Jeśli długości najkrótszych ścieżek s. przed u. i z s. przed v. dopasować się.

Algorytm Daekstra konsekwentnie usprawnia wierzchołki wykresu w sensie bliskości do góry s. oraz w oparciu o następujące podstawowe zasady.

Jeśli długości łuku to liczby dodatnie, to

najbliższy K. s. top - sama. Długość najkrótszej ścieżki s. przed s. równy 0;

najbliższy K. s. wierzchołek s., Leży z s. W odległości jednego łuku  najkrótsze ze wszystkich łuków pozostawiając szczyt s.;

dowolna pośrednia górnacz najkrótszej ścieżki s. Do niektórych wierzchołków v. Leży bliżej K. s.niż ostatni wierzchołek v.;

najkrótsza droga do następnego zamówionego wierzchołka może przejść tylko przez już zamówione szczyty.

Niech algorytm już zamówił szczyty v. 1 , v. 2 … v. k. . Oznaczać
,
Długość najkrótszej ścieżki na górę v. jA. .

Rozważ wszystkie łuki z wykresu źródłowego, który rozpoczyna się w jednym z wierzchołków zestawu.
I kończy się w innym nieuporządkowanym wierzchołku. Dla każdego takiego łuku na przykład
, Obliczę sumę
. Kwota ta jest równa długości ścieżki s. w y.W którym wierzchołek v. jA. Jest przedostatni wierzchołek, a ścieżka s. w v. jA. - Najkrótsze ze wszystkich ścieżek łączących się s. i v. jA. .

Jest to najbardziej zdefiniowane długości wszystkich ścieżek s. Nie zamówiono jeszcze szczytów, w których tylko wierzchołki są wierzchołkami pośrednimi k. Najbliższy K. s.. Niech najkrótszy z tych ścieżek kończy się na górze w.. Następnie w. i jest
Przez bliskość K. s. wierzchołek.

Technicznie działania na algorytmie DaEkstra są przeprowadzane za pomocą urządzenia do znakowania wierzchołka. Tag Verth. v. oznacza sposób
. Każda etykieta jest liczbą równą długości niektórych ścieżki s. przed v.. Tagi są podzielone na tymczasową i stałą. Na każdym kroku tylko jedna etykieta staje się stała. Oznacza to, że jego wartość jest równa długości najkrótszej ścieżki do odpowiedniego wierzchołka, a ten sam wierzchołek jest uporządkowany. Liczba następnego zamówionego wierzchołka jest oznaczona literą r..

Opis algorytmu.

Krok 1. (Instalacja wstępna). Położyć
I rozważ tę stałą etykiet. Położyć
,
I rozważ te znaki tymczasowe. Położyć
.

Krok 2. (Współdzielony krok). On powtarza n. po zamówieniu wszystkich wierzchołków wykresu.

Przeliczyć tymczasowy znak
Wszystkie nieuporządkowane wierzchołki v. jA. który obejmuje łuk opuszczający górę r, Z reguły

Wybierz górę z minimalną etykietą czasu. Jeśli jest kilka takich wierzchołków, wybierz dowolną.

Zostawiać w.- Góra z minimalną etykietą czasu. Weź etykietę
stała i umieszczona
.

Kroki algorytmu Daekstra są wygodnie sporządzone w tabeli, której każda kolumna odpowiada wierzchołek wykresu. Rzędy tabeli odpowiadają powtórzeniu ogólnego kroku.

Przykład. Na wykres na rys. 4. Znajdź najkrótsze ścieżki wierzchołków
do wszystkich innych wierzchołków wykresu. Żebra oznaczają dwa wielokierunkowe łuki o tej samej długości.

Decyzja. W zakładce. 1 Nagrane znaczniki wierzchołków na każdym kroku. Tagi stałe są oznaczone "+". Opiszmy szczegółowo, jak obliczane są znaczniki.

Z Vertex 1 Arcs z widokiem na wierzchołki 2, 5, 6. Przywołując etykiety tych wierzchołków i wypełnić drugi ciąg tabeli.

Góra wierzchołka 6 staje się stała,
.

Z łuków VEREX 6 są nadal nieuporządkowane wierzchołki 2, 5, 8, 9. Przeliczają swoje znaczniki czasowe

Wypełnij 3 rzędy stołu. Minimum etykiet czasu to 3 (najlepsza tag 9),
.

Z łuku wierzchołka 9 wciąż nieuporządkowane wierzchołki 5, 8, 11, 12. Następnie

Wypełnij czwartą linię stołu. W tej linii dwa wierzchołki  2 i 12 mają minimalne znaczniki czasowe równe 4. Pierwsze zamówienie, na przykład, wierzchołek 2. Następnie górny 12 zostanie zamówiony w następnym kroku.

Tabela 1

Więc,
.

Z pierwszej 2 znajdują się łuki wciąż nieuporządkowane wierzchołki 3, 4, 5. Przywołując tymczasowe znaki tych wierzchołków

Wypełnij 5 wierszy stołowych. Minimum etykiet czasu to 4 (tag wierzchołka 12),
.

Wypełnij 6 rzędów stołu. Minimalne etykiety czasowe to 5 (najlepsza tag 5),
.

Wypełnij 7 ciąg stołu. Stać się ciągłym znacznikiem wierzchołka 8 (jest równa 5),
.

Top 11 jest zamówiony.

Od łuków VEREX 11 w nieuporządkowanych wierzchołkach 7 10. Przywołując znaki czasu tych wierzchołków.

Top 4 dostaje stałą tag.

Z łuku VEREX 4 w uśmierconych wierzchołkach 3, 7. Przekonaj znaczniki czasowe

Organizuj wierzchołek 3.

Wypełnij 12 wierszy stołowych. W tym kroku zamawiamy ostatnie nieuporządkowane wierzchołek 10.

Budowanie drzewa najkrótszych ścieżek.

Drzewo najkrótszych ścieżek to skupione drzewo z korzeniem na górze S. . Wszystkie ścieżki w tym drzewie są najkrótsze dla tego wykresu.

Najkrótsze drzewo ścieżki opiera się na stole, górna jest włączona na wierzchołek w kolejności, w jakiej otrzymywali stałe tagi. Pierwszy na drzewie włącza się na root - wierzchołek S. .

Konstruujemy najkrótsze drzewo dla naszego przykładu.

Po pierwsze, włączamy korzeń na drzewie - wierzchołek 1. Następnie łuk jest przekształcony w drzewo (1,6). Następny został zamówiony wierzchołek 9, długość najkrótszej ścieżki, do której jest równa 3. Pierwszy raz numer 3 pojawił się w trzecim wierszu, który został wypełniony
. W związku z tym wierzchołek 6 jest przedostatnią górną górą najkrótszej ścieżki do wierzchołka 9. Włączymy w łuku drewna (6.9) długość 1.

Top 2 został zamówiony długością najkrótszej ścieżki równej 4. Numer ten po raz pierwszy pojawił się w trzecim wierszu, który został wypełniony
. W związku z tym najkrótsza ścieżka w drugim wierzchołku przechodzi wzdłuż łuku (6.2). Włączamy łuk (6.2) długości 2.

Następnie zamówiono 12 najlepszych,
. Pierwszy raz numer 4 pojawia się w czwartej linii, która była wypełniona
. Drzewo zawiera łuk (9.12) długości 1. Całkowite drzewo najkrótszych ścieżek pokazano na FIG. pięć.

Algorytm deiquita może być nie tak, jeśli w kolumnie są negatywne łuki. Więc szukając najkrótszych ścieżek z góry s. \u003d 1 na wykres na rys. 6, algorytm najpierw zamówił wierzchołek 3, a następnie wierzchołek 2 i zakończ pracę. W tym przypadku ta najkrótsza droga do góry 3, z punktu widzenia algorytmu Daeksstra,  to Długość ARC (1.3) 3.

W rzeczywistości najkrótsza droga do Vertex 3 składa się z łuków (1.2) i (2.3), długość tej ścieżki wynosi 5 + (- 3) \u003d 2.

Ze względu na obecność łuku (2.3) długości ujemnej -3, zakłócono następujące podstawowe zasady:

najbliższy K. s. Szczyt leży od niego w odległości dwóch łuków, a nie jeden;

pośredni góra najkrótszej ścieżki 1-2-3 (wierzchołka 2) leży dalej od wierzchołka 1 (w odległości 5) niż końcowy wierzchołek ścieżki 3.

W konsekwencji obecność łuku negatywnego długości komplikuje rozwiązanie problemu najkrótszej ścieżki i wymaga stosowania bardziej złożonych algorytmów, a nie algorytm Daekstra.

Rozwiąż zadanie znalezienia najkrótszej ścieżki algorytmu DaEkstra.
Znajdź najkrótszą ścieżkę z X0 do X7. Liczba jest ustawiana przez elementy matrycy kosztów

Zbuduj ten wykres


Zacznijmy od elementu X0 i przypisujemy go znacznik 0, uważaj wszystkich swoich sąsiadów, ponieważ Nadal nie ma uwagi, przypisujesz im odpowiednie długości:


Wszyscy sąsiedzi X0 są brane pod uwagę, zaznaczamy go i idzie na górę X1. Sąsiedzi X0, X2, X4, ale X0 oznaczone, nie uważają tego. Dla x2: , Zostaw etykietę.

Dla x4: Wymiana etykiety. Wszyscy sąsiedzi Vertex X1 są brane pod uwagę, zaznaczamy to


Idź na górę x2. Sąsiedzi X0, X1, X3, X4, X5, X6, ale x0, X1 są oznaczone, nie uważaj ich.
Dla x3: , Zostaw etykietę.
Dla x5: Wymiana etykiety.
Dla x4: , Zostaw etykietę.
Dla x6: Wymiana etykiety.
Uważamy, że wszyscy sąsiedzi górnej części X2, zaznaczamy to.


Idź do góry X3. Jego sąsiedzi x0, x2, x6, ale x0, x2 są oznaczone, nie uważają ich.
Dla x6: , Zostaw etykietę.
Wszyscy sąsiedzi szczytu X3 są brane pod uwagę, zaznaczamy to.


Idź na górę x4. Jego sąsiedzi x1, x2, x5, x7, ale x1, x2 są zaznaczone, nie uważaj ich.
Dla x5: Wymiana etykiety.
Dla x7: Wymiana etykiety.
Wszyscy sąsiedzi szczytu X4 są brane pod uwagę, zaznaczamy to.


Idź na górę X5. Jego sąsiedzi x2, x4, x6, x7, ale x2, x4 są zaznaczone, nie uważaj ich.
Dla x6: , Zostaw etykietę.
Dla x7: , Zostaw etykietę.
Wszyscy sąsiedzi szczytu X5 są brane pod uwagę, zaznaczamy to.


Idź na górę x6. Jego sąsiedzi x2, x3, x5, x7, ale x2, x3, x5 są zaznaczone, nie uważaj ich.
Dla x7: , Zostaw etykietę.
Rozważane są wszystkie blaty X6, zaznaczamy to. I oznaczaliśmy pozostałe X7, wszystkie wierzchołki są brane pod uwagę.


Wniosek: Najkrótsza ścieżka ich X0 w X7 ma długość 101, ta ścieżka: X7-X4-X1-X0.