Область применения

Алгоритм Дейкстры широко применяется в программировании, так как позволяет решать целый ряд задач, связанных с поиском оптимального пути.

Также, он применяется в протоколе маршрутизации OSPF–динамическом протоколе, основанном на технологии отслеживания состояния канала(link-statetechnology) и использующий для нахождения кратчайшего пути алгоритм Дейкстры.

Протокол OSPF был разработан IETF в 1988 году. Последняя версия протокола представлена в RFC 2328. Протокол OSPF представляет собой протокол внутреннего шлюза (InteriorGatewayProtocol — IGP). Протокол OSPF распространяет информацию о доступных маршрутах между маршрутизаторами одной автономной системы.

OSPF имеет следующие преимущества:

· Высокая скорость сходимости по сравнению с дистанционно-векторными протоколами маршрутизации;

· Поддержка сетевых масок переменной длины (VLSM);

· Оптимальное использование пропускной способности с построением дерева кратчайших путей;

Как работает этот протокол:

1. Маршрутизаторы обмениваются hello-пакетами через все интерфейсы, на которых активирован OSPF. Маршрутизаторы, разделяющие общий канал передачи данных, становятся соседями, когда они приходят к договоренности об определённых параметрах, указанных вихhello-пакетах.

2. На следующем этапе работы протокола маршрутизаторы будут пытаться перейти в состояние смежности со своими соседями. Переход в состояние смежности определяется типом маршрутизаторов, обменивающихсяhello-пакетами, и типом сети, по которой передаются hello-пакеты. OSPF определяет несколько типов сетей и несколько типов маршрутизаторов. Пара маршрутизаторов, находящихся в состоянии смежности, синхронизирует между собой базу данных состояния каналов.

3. Каждый маршрутизатор посылает объявления о состоянии канала маршрутизаторам, с которыми он находится в состоянии смежности.

4. Каждый маршрутизатор, получивший объявление от смежного маршрутизатора, записывает передаваемую в нём информацию в базу данных состояния каналов маршрутизатора и рассылает копию объявления всем другим смежным с ним маршрутизаторам.

5. Рассылая объявления внутри одной OSPF-зоны, все маршрутизаторы строят идентичную базу данных состояния каналов маршрутизатора.

6. Когда база данных построена, каждый маршрутизатор использует алгоритм «кратчайший путь первым» для вычисления графа без петель, который будет описывать кратчайший путь к каждому известному пункту назначения с собой в качестве корня. Этот граф — дерево кратчайших путей.

7. Каждый маршрутизатор строит таблицу маршрутизации из своего дерева кратчайших путей.

Также, алгоритм Дейкстры применяется в протоколе маршрутизации промежуточных систем (IS-IS) - протокол внутренних шлюзов (IGP), стандартизированный ISO и использующийся в основном в крупных сетях провайдеров услуг. IS-IS может также использоваться в корпоративных сетях особо крупного масштаба. IS-IS — это протокол маршрутизации на основе состояния соединений. Он обеспечивает быструю сходимость и отличнуюмасштабируемость. Как и все протоколы на основе состояния соединений, IS-IS очень экономно использует пропускную способность сетей.

Приложение «Алгоритм Дейкстры для поиска кратчайшего пути» имеет расширение .exe и, следовательно, работает только в ОС Windows.

Требования к системе:

1) ОС WindowsXP или более поздние версии;

2) Direct X 9;

3) 10 Мб свободного места на жестком диске;

4) Видеоускоритель;

5) Устройства ввода(мышь, клавиатура).