Въведение в алгоритъма SPF

Алгоритъмът на Dijkstra обикновено се нарича алгоритъм за най-кратък път (SPF).

Това SPF алгоритъм натрупва разходи по всеки път от източника до местоназначението. Въпреки че алгоритъмът на Дейкстра е известен като алгоритъм за предпочитание на най-краткия път, това всъщност е целта на всеки алгоритъм за маршрутизиране.

На фигурата всеки път е обозначен със случайна стойност на разходите. Най-краткият път за R2 за изпращане на пакети по LAN, прикрепен към R3, е 27. Имайте предвид, че този разход не е 27 за всички рутери, за да достигнат LAN, прикрепен към R3. Всеки рутер определя собствените си разходи за всяка дестинация в топологията. С други думи, всеки рутер изчислява алгоритъма SPF и определя цената от своя собствена перспектива. Това ще стане по-очевидно по-късно в този раздел.

Щракнете върху 2 на снимката.

За R1 най-краткият път до всяка локална мрежа - заедно с разходите - е показан в таблицата. Най-краткият път не е непременно пътят с най-малко хмел. Например погледнете пътя към LAN R5. Може би си мислите, че R1 ще предава директно на R4, а не на R3. Въпреки това, цената за директно достигане до R4 (22) е по-висока от цената за достигане до R4 чрез R3 (17).

Продължавайте да превключвате бутони 3, 4, 5, 6 на снимката.

Проследете най-краткия път за всеки рутер, за да достигнете до всяка LAN, както е показано в таблиците.