W poprzednich wykładach rozmawialiśmy o implementacji algorytmu Dijkstry i zobaczmy, czy
działa dobrze, czy nie.
Więc jeśli nazwa jest równa main, to jest to główna funkcja.
Przede wszystkim musimy utworzyć wierzchołki lub węzły.
Stworzymy wykres, o którym mówiliśmy w części teoretycznej.
Przepraszam za to.
Skonstruowałem już wykres.
Mamy więc osiem węzłów, A, B, C, D, E, F, G i H.
Wtedy oczywiście musimy zająć się i stworzyć krawędzie.
Są to oczywiście krawędzie skierowane, ponieważ jest to wykres skierowany.
Niestety mamy kilka krawędzi.
Raz, dwa, trzy, cztery, pięć do 16 lat.
Jak widać, między podanymi wierzchołkami jest 16 skierowanych krawędzi o różnych krawędziach.
Więc to jest wykres, o którym rozmawialiśmy z wierzchołkami i krawędziami, jeśli chodzi o
wagi.
Zobaczmy, czy działa dobrze, czy nie.
Oczywiście musimy poradzić sobie z sąsiadami.
Zatem pierwszy węzeł ma trzy krawędzie, krawędź pierwszą, drugą i trzecią.
Lista przylegania nie będzie przechowywać sąsiednich wierzchołków.
Będzie przechowywać krawędzie.
Tak więc przechowujemy dzieci.
Ale zasadniczo krawędzie będą reprezentować sąsiadów, ponieważ oczywiście każda pojedyncza krawędź ma wierzchołek początkowy
i wierzchołek docelowy.
Zatem wierzchołek celu związany z krawędzią jest sąsiadem rzeczywistego węzła.
Okay, więc w ten sposób tworzymy wierzchołki, krawędzie i tak postępujemy z przyległościami.
A potem musimy tylko uruchomić aplikację.
Mamy więc algorytm równy algorytmowi Dijkstry.
Okay, musimy wywołać funkcję obliczającą i musimy zdefiniować wierzchołek początkowy.
Początkowym wierzchołkiem jest pierwszy wierzchołek wierzchołka A, a następnie musimy wywołać algorytm dokładną najkrótszą
ścieżką i musimy zdefiniować węzeł.
Chcielibyśmy obliczyć najkrótszą drogę.
Na przykład węzeł ósmy, oczywiście, węzeł ósmy to wierzchołek G.
Jeśli więc zapiszemy i uruchomimy aplikację, najkrótsza ścieżka do Vertex to osiem.
Oczywiście nie działa dobrze.
Przepraszam za to.
Przede wszystkim musimy to sprawdzić, chociaż faktyczny wierzchołek nie jest Ainun, więc nie jest faktycznym wierzchołkiem, ale
jest to konieczne.
Więc jeśli powtórzymy, będzie trochę lepiej.
W porządku.
I działa dobrze.
Przepraszam za to.
Popełniłem błąd, ponieważ węzeł osiem jest węzłem wieku, ale szukam węzła siedem, jeśli chodzi
o GS.
Więc jeśli spróbujemy Node siedem i ponownie uruchomimy aplikację, to najkrótsza ścieżka, Vertex G, będzie równa
dwudziestu pięciu.
Oczywiście to właśnie obliczyliśmy w części teoretycznej.
A jaka jest najkrótsza droga, którą musimy przejść od A do E do F, F do C CTG.
Czyli 82 F, F do C i CTG.
OK, więc tak działa niebezpieczny algorytm.
Zobaczmy, jaka jest najkrótsza ścieżka do węzła F, na przykład jeśli chodzi o sześć.
Więc jeśli ponownie uruchomimy aplikację, to najkrótsza ścieżka, wierzchołek F to trzynaście F, E i A, mamy
wierzchołki F A do E do F i minimalne odległości trzynaście jednostek.
Tak więc możemy zaimplementować niebezpieczny algorytm w Pythonie.
Dzięki za oglądanie.