Ako smerovacie algoritmy Work

budeme používať tento algoritmus ako príklad na ďalšej strane
. Príklad :. Dijkstra algoritmus
Krok 1
Krok 2 Krok 3
krok 4

Tu chceme nájsť najlepšiu trasu medzi A a E (pozri nižšie). Môžete vidieť, že existuje šesť možné cesty medzi A a E (ABE, ACE, abde, ACDE, ABDC, ACDBE), a je zrejmé, že abde je najlepšia cesta, pretože jeho hmotnosť je najnižšia. Ale život nie je vždy tak jednoduché, a tam sú niektoré zložité prípady, kedy máme použiť algoritmy nájsť najlepšiu trasu.

1. Ako vidíte na prvom obrázku, zdrojový uzol (A) bol vybraný ako T-uzol, a tak jeho značka je trvalá (ukážeme trvalé uzly s vyplnenými kruhmi a T-uzly, ktoré majú - > symbolu).
   
2. V ďalšom kroku, uvidíte, že stav sada záznamov predbežných uzlov priamo spojených s T-uzla (B, C), bol zmenený. Tiež, pretože B má menšiu váhu, že bol vybraný ako T-spoje a štítkom sa zmenil na trvalé (pozri nižšie).
   
3. V kroku 3, rovnako ako v kroku 2, stav záznamu súboru predbežných uzlov ktoré majú priamu väzbu na T-uzla (D, E), bol zmenený. Tiež, pretože D má menšiu váhu, to bolo vybrané ako T-uzol a štítkom sa zmenilo na trvalé.
   
4. V kroku 4, nemáme žiadne opatrné uzly, a tak sme hneď identifikovať ďalšie T -node. Vzhľadom k tomu, E má najmenšiu váhu, to bolo vybrané ako T-uzol.
   

   A konečne, E je cieľ, a tak sme tu zastaviť.
   

   Sme na konci! Teraz musíme určiť trasu. Predchádzajúci uzol E je D, a predchádzajúce uzol D je B, a B je predchádzajúci uzol A. Takže najlepšia cesta je abde. V tomto prípade je celková hmotnosť je 4 (1 + 2 + 1).
   

   Hoci tento algoritmus funguje dobre, je to tak zložité, že to môže trvať dlhý čas pre routery je spracovávať, a účinnosti sieť zlyhá. Aj v prípade, router dáva zlé informácie pre ostatné smerovače, všetky smerovacie rozhodnutie bude neúčinná. Pre lepšie pochopenie tohto algoritmu, tu je zdrojom programu napísané C:
   

    #define MAX_NODES 1024 /* maximálny počet uzlov * /# define INFINITY 1000000000 /* číslo väčšie ako každý maximálnu cesta * /int n, dist [MAX_NODES] [MAX_NODES]; /* Dist [I] [j] je vzdialenosť od i do j * /void shortest_path (int s, int t, int path []) {struct stav {/* cesta sa pracuje * /int predchodcu; /* Predchádzajúca dĺžka uzla * /int /* dĺžka od prameňa k tomuto uzlu
   Page     [1] [2] [3] [4] [5] [6]