Algorytm Dijkstry C ++

Algorytm Dijkstry jest również znany jako najkrótszy możliwy algorytm ścieżki. Procedura jest znalezienie najkrótszej ścieżki między węzłami/ krawędziami wykresu. Najkrótszy wykres drzewa jest tworzony przez początek od wierzchołka źródłowego do wszystkich pozostałych punktów na wykresie.

Algorytm

• Przed bezpośrednim wdrożeniem wykresu Dijkstra w języku programowania C ++ musimy zrozumieć działanie tego algorytmu wykresu.
• Pierwszym krokiem jest stworzenie „Sptset”, które jest skrócone jako najkrótszy zestaw drzew ścieżki; przechowuje zapis tych wierzchołków, które są zawarte na najkrótszej ścieżce. Na początkowym etapie zestaw ten jest deklarowany jako zerowy.
• W następnym kroku, po pierwsze, wszystkie te wartości w węzłach są deklarowane jako nieskończone, ponieważ do tej pory nie znamy ciężaru ścieżek.
• Wybierz Vertex „U”, który nie jest już obecny w SPTSET i ma minimalną wartość. Następnie dołącz go do Sptset. Następnie zaktualizuj wartości odległości wszystkich tych węzłów, które są sąsiadującymi wierzchołkami „u.„To wszystko odbywa się pod pętlą, dopóki SPTSET nie będzie w stanie zawierać wszystkich wierzchołków.

Wdrożenie algorytmu wykresu Dijkstra

Oto implementacja wykresu Dijkstra, w której program jest zapisywany dla reprezentacji macierzy przylegania tego wykresu. Rozpocznij program, dodając dwie biblioteki bardzo niezbędne do osiągnięcia programu w języku programowania C ++, który sprawia, że ​​możemy korzystać z funkcji CIN i COUT.

#włączać
#włączać

Po opisaniu bibliotek, teraz zapewnimy rozmiar lub wierzchołki wykresu, na którym potrzebujemy najkrótszej ścieżki. Podaliśmy 9 wierzchołków, co oznacza, że ​​matryca jest kwadratem [9] [9].

#definicja V 9

„V” dotyczy wierzchołków. Ponieważ algorytm wymaga wielu kroków, aby wykonać dostarczone zadanie, każdy krok lub proces jest podzielony na osobne funkcje, aby je wykonać, aby kod był jasny i nie ma dwuznaczności dotyczącej logiki. Ponadto złożoność jest również usuwana.

Funkcja jest tutaj tworzona w celu przeszukania wierzchołka, która ma minimalną wartość odległości; Zawiera zestaw wierzchołków, które nie są zawarte w drzewie o najkrótszej ścieżce. Funkcja będzie zawierać tablicę odległości i spset typu bool, najkrótszy zestaw drzew ścieżki i tablicę jako parametr funkcji. Wewnątrz funkcji minimalna wartość jest inicjowana poprzez deklarowanie zmiennej typu liczb całkowitych, która będzie przechowywać zwróconą wartość. Wprowadzono dwie zmienne, Max i min_index.

Int min = int_max, min_index;

Pętla jest tutaj używana; w którym pobierany jest początkowy wierzchołek we wszystkich wierzchołkach, pętla będzie kontynuowana do momentu przejścia wszystkich wierzchołków. Warunek jest tutaj stosowany za pomocą instrukcji IF, która sprawdza, czy najkrótszy zestaw ścieżki jest fałszywy, jest teraz pusty, a odległość wierzchołka jest mniejsza niż w przypadku minimalnej wartości wierzchołka, który jest wcześniej zadeklarowany, następnie przydziel bieżącą wartość wierzchołka jako min, a min_index będzie również zawierać tę samą wartość wierzchołka.

Min = dist [v], min_index = v;

Po obliczeniu minimalnej wartości wierzchołka następnego jest proces tworzenia funkcji, która wyświetli tablicę odległości, która została wcześniej skonstruowana. Pętla iteruje każdy indeks, który zostanie dostępny i wyświetlany. Najpierw wyświetlany jest liczba wierzchołków, zaczynając od wartości zerowej, a odległość wierzchołka od źródła jest również wymieniona tutaj z sekwencją. Ta funkcja jest tutaj zadeklarowana, ale zostanie wywołana później w programie, gdy cała ścieżka zostanie obliczona jako najkrótsza odległość.

Główna część całego kodu źródłowego jest teraz zadeklarowana, gdzie obliczana jest implementacja najkrótszej ścieżki. Wykres będzie reprezentowany przez reprezentację macierzy sąsiedności. Ta funkcja przyjmuje macierz wykresu i źródło jako wartości parametrów, które będą działać jako wejście do obliczenia odległości. Po pierwsze, wewnątrz funkcji zadeklarujemy tablicę wyjściową, która będzie zawierać najkrótszą ścieżkę od źródła do określonego punktu. Po drugie, deklarowana jest tablica zmiennej logicznej, która zwróci prawdziwie, jeśli wierzchołek zostanie uwzględniony przy określaniu najkrótszej ścieżki na początku.

Int dist [v]; Bool sptset [v];

Wszystkie odległości zostaną ustawione jako nieskończone, a najkrótsza tablica ścieżki drzewa jest fałszywa. Za pomocą pętli będzie miał miejsce cały ten proces.

Wewnątrz pętli, wierzchołek minimalnej odległości jest zbierany z zestawu wierzchołków, które jeszcze nie są przetwarzane. W pierwszej iteracji „u” jest zawsze równe źródłem wierzchołku.

Int u = Mindistance (Dist, Sptset);

Te wierzchołki, które są wybrane i przemierzone, są zbierane i oznaczone jako przetwarzane przez ustawienie zmiennej logicznej, jest prawdziwa.

sptSet [u] = true;

Po dodaniu jednego wierzchołka sprawdzane są również wszystkie wierzchołki przylegające do tego konkretnego wierzchołka; To wymaga aktualizacji. Zaktualizujemy więc wartość „dist” sąsiednich wierzchołków tych wierzchołków, które były do ​​tej pory pikiety.

Wewnątrz pętli zaktualizujemy Dist [v], jeśli i tylko wtedy, gdy nie ma go w SPTSET, istnieje linia zwana krawędzią od wierzchołka U do V, a całkowita waga ścieżki zaczyna się od „SRC” do „v”, przechodząc przez „u” jest mniejszy niż bieżąca wartość obecna w Dist [v].

Dist [v] = dist [u] + wykres [u] [v];

Następnie funkcja wydruku, którą zadeklarowaliśmy powyżej, jest wywoływana przez przekazywanie tablicy Dist [] jako parametr.

PrintSolution (Dist);

W programie głównym tworzymy wykres macierzy 9*9. A następnie wykonane jest wywołanie funkcji dla funkcji Dijkstra, przez które wykres jest przekazywany.

Zapisz cały kod. Skompiluj kod za pomocą kompilatora G ++ w terminalu Ubuntu. „-O” to symbol, który zapisuje dane wyjściowe pliku.

$ g ++ -o dij dij.C
$ ./Dij

Możesz zobaczyć, że wszystkie wierzchołki w każdej osobnej linii są wyświetlane wraz z odległością każdego wierzchołka od źródła.

Ten kod pomaga obliczyć najkrótszą odległość, ale nie obsługuje obliczania informacji o ścieżce. Ten kod źródłowy jest dobry dla nieokreślonych wykresów, ale może być możliwy również do użycia dla ukierunkowanych wykresów. Korzystając z tego kodu, możemy znaleźć najkrótszą odległość od punktu źródła do wszystkich innych wierzchołków na wykresie.

Złożoność czasu Dijkstra

Porozmawiamy o złożoności czasowej wdrożenia. To jest:

0 (V^2).

Można to zmniejszyć do 0 (e log v) za pomocą procesu sterty binarnej. Wykres Dijkstra nie dotyczy wykresów, które mają ujemne wagi.

Wniosek

Ten artykuł zawiera proces znajdowania najkrótszej odległości między węzłem źródłowym do reszty węzłów. Może być do tego wiele podejść. Ale wykres Dijkstra jest jednym z najlepszych mechanizmów w tym celu. Jest przeznaczony do nieokreślonych wykresów. Wyjaśniliśmy proces krok po kroku z kodem źródłowym, aby był żywy dla nowych użytkowników. Mamy nadzieję, że ten wysiłek będzie odpowiedni dla czytelników.