budeme používat tento algoritmus jako příklad na další straně
. Příklad:. Dijkstra algoritmus
Krok 1
Krok 2 Krok 3
Krok 4
Zde chceme najít nejlepší trasu mezi A a E (viz níže). Můžete vidět, že existuje šest možné cesty mezi A a E (ABE, ACE, Abde, ACDE, ABDCE, ACDBE), a je zřejmé, že Abde je nejlepší cesta, protože jeho hmotnost je nejnižší. Ale život není vždy tak snadné, a tam jsou některé složité případy, kdy máme použít algoritmy najít nejlepší trasu.
- Jak vidíte na prvním obrázku, zdrojový uzel (A) byl vybrán jako T-uzel, a tak jeho značka je trvalá (ukážeme trvalé uzly s vyplněnými kruhy a T-uzly, které mají - > symbolu).
- V dalším kroku, uvidíte, že Stav sada záznamů předběžných uzlů přímo spojených s T-uzlu (B, C), byl změněn. Také, protože B má menší váhu, že byl vybrán jako T-spoje a štítkem se změnil na trvalé (viz níže).
- V kroku 3, stejně jako v kroku 2, stav záznamu souboru předběžných uzlů které mají přímou vazbu na T-uzlu (D, E), byl změněn. Také, protože D má menší váhu, to bylo vybráno jako T-uzel a štítkem se změnilo na trvalé.
- V kroku 4, nemáme žádné opatrné uzly, a tak jsme hned identifikovat další T -uzel. Vzhledem k tomu, E má nejmenší váhu, to bylo vybráno jako T-uzel.
A konečně, E je cíl, a tak jsme tady zastavit.
Jsme na konci! Nyní musíme určit trasu. Předchozí uzel E je D, a předchozí uzel D je B, a B je předcházející uzel A. Takže nejlepší cesta je Abde. V tomto případě je celková hmotnost je 4 (1 + 2 + 1).
Ačkoli tento algoritmus funguje dobře, je to tak složité, že to může trvat dlouhou dobu pro routery je zpracovávat, a účinnosti Síť se nezdaří. Také v případě, router dává špatné informace pro ostatní směrovače, všechny směrovací rozhodnutí bude neúčinná. Pro lepší pochopení tohoto algoritmu, tady je zdrojem programu napsané C:
#define MAX_NODES 1024 /* maximální počet uzlů * /# define INFINITY 1000000000 /* číslo větší než každý maximální cesta * /int n, dist [MAX_NODES] [MAX_NODES]; /* dist [I] [j] je vzdálenost od i do j * /void shortest_path (int s, int t, int path []) {struct stav {/* cesta se pracuje * /int předchůdce; /* předchozí délka uzlu * /int /* délka od pramene k tomuto uzlu * /enum {trvalý, orientační} Etiketa /* Stát štítek * /} state [MAX_NODES], int i, k, min; struct stav * p; pro (p = & stavu [0]; p < & stav [n], p ++)
