Będziemy używać tego algorytmu jako przykład na następnej stronie
Przykład:.. Dijkstra algorytmu
Krok 1
Krok 2 Step 3 Step 4 Największa
Tutaj chcemy znaleźć najlepszą trasę pomiędzy A i E (patrz poniżej). Widać, że istnieje sześć możliwych tras pomiędzy A i E (ABE, ACE, ABDE, ACDE, ABDCE, ACDBE), i to jest oczywiste, że ABDE jest najlepsza droga, ponieważ jego waga jest najniższy. Ale życie nie zawsze jest tak łatwo, i są pewne skomplikowane przypadki, w których mamy do wykorzystania algorytmów, aby znaleźć najlepszą trasę. Największa
- Jak widać na pierwszym zdjęciu, węzeł źródłowy (A) została wybrana jako T-węzła, a więc jego etykieta jest stała (pokażemy stałe węzły z wypełnionych okręgów i T-węzłów z - > symbol). Największa
- W następnym kroku, można zauważyć, że zapis stanu zestaw wstępnych węzłów bezpośrednio związane z T-węzła (B, C) został zmieniony. Ponadto, ponieważ B ma mniejszą wagę, został wybrany jako T-węzła i jego wytwórnia zmieniła się na stałe (patrz poniżej). Największa
- W punkcie 3, jak w kroku 2, zbiór rekord status wstępnych węzłów które mają bezpośredni związek z T-węzła (D, E), został zmieniony. Ponadto, ponieważ D ma mniejszą wagę, został wybrany jako T-węzła i jego wytwórnia zmieniła się na stałe. Największa
- W punkcie 4, nie mamy żadnych wstępne węzłów, więc po prostu określić następny T -węzeł. Od E ma najmniejszą wagę, został wybrany jako T-węzła.
Na koniec, E jest cel, więc tutaj zatrzymać. Największa
Jesteśmy w końcu! Teraz musimy określić trasy. Poprzednim węzłem E jest D, a poprzedni węzeł D jest B, a poprzedni węzeł B jest A. Tak więc najlepszym sposobem jest ABDE. W tym przypadku całkowita ważą jest 4 (1 + 2 + 1). Największa
Mimo, że ten algorytm działa dobrze, to jest tak skomplikowane, że może to zająć dużo czasu, aby je przetwarzać routery i sprawność Sieć nie. Ponadto, jeśli router daje błędne informacje do innych routerów, wszystkie decyzje routingu
