Определение кратчайшего пути от одного узла до другого | Выбор сетевого оборудования. Обзоры, настройка, сравнение характеристик. | Ofisp.org

Определение кратчайшего пути от одного узла до другого

Для определения кратчайшего пути от одного узла до другого Дейкстра предложил следующий алгоритм. Топология сети представляется в виде неориентированного графа с указанными для каждого ребра значениями метрики (например, расстояния между двумя соседними узлами). Изначально путь неизвестен, поэтому все вершины графа получают метки с бесконечным значением расстояния до отправителя. Метки могут быть временными или постоянными.

Пусть требуется найти кратчайший путь от А до Z. Сначала узел А получает постоянную метку и делается текущим узлом. Затем мы просматриваем все соседние узлы (с которыми вершина А соединена ребром) и отмечаем расстояние до А. После того как все соседние узлы перебраны, узел с наименьшей меткой выбирается в качестве текущего, при этом он получает постоянную метку. Пусть это будет узел B. Теперь мы просматриваем все соседние узлы, и если сумма расстояний от B до А и от данного узла до B меньше значения метки этого узла, то он получает новую метку, причем мы указываем, что путь в А лежит через B, чтобы после завершения процедуры можно было восстановить маршрут. После перебора всех соседних узлов мы вновь ищем по всему графу вершину с наименьшей временной меткой и выбираем этот узел в качестве текущего, при этом он получает постоянную метку и т. д.

Похожие материалы

24.12.2013
В последние несколько лет сама необходимость в маршрутизаторах начала подвергаться сомнению, главным образом в связи с появлением и распространением коммутаторов (по сути многопортовых мостов). В чем же причины того, что пользователи начали устанавливать в своих сетях коммутаторы там, где они раньше использовали маршрутизаторы?
24.12.2013
Основная масса IPсетей может быть выстроено при помощи всего 2-ух типов приборов: коммутаторов (концентраторов) и маршрутизаторов. Назначение первых мы уже разбирали, наступило время пообщаться о вторых – маршрутизаторах. В этой статье пойдет речь про то, что же такое маршрутизатор и для чего он необходим. Коммутаторы позволяют совместить сетевые приспособления в общий сегмент сети с единой IP адресацией (например, у нас есть компьютер с адресом 172.20.20.20/24 и 172.20.20.21/24, просто втыкаем их в коммутатор и они уже видят друг друга – образуют единый сегмент сети).
24.12.2013
В предшествующем разделе под словом "маршрутизатор" подразумевался прежде всего IP-маршрутизатор, т. е. что он предназначен только для продвижения IP-пакетов. Однако маршрутизаторы могут работать и с пакетами других протоколов сетевого уровня, например с IPX. Таким образом, кроме IP-маршрутизаторов есть еще IPX-маршрутизаторы и др.
24.12.2013
В качества примера мы рассмотрим определение таблицы на маршрутизаторе компании Morning Star с тремя интерфейсами: одним интерфейсом Ethernet, последовательным портом, подключенным к внешнему модему, и интерфейсом глобальной сети frame relay (см. Таблицу).
24.12.2013
Маршрутизаторы часто путают с мостами. А "Вебстерский словарь компьютерных терминов" вообще пишет, что маршрутизатор - это другое название моста. Такое положение дел объясняется тем, что многие устройства сочетают в себе функции и мостов, и маршрутизаторов."Чистый" мост анализирует заголовки кадра канального уровня и не просматривает (а тем более не модифицирует) пакеты сетевого уровня внутри пакетов. Мост не знает и не должен знать, какие пакеты - IP, IPX или CLNP - содержит в поле полезной нагрузки кадр, передаваемый из локальной сети 802.х в 802.y.

Оборудование:

Общие характеристики Тип: Wi-Fi точка доступа Стандарт беспроводной связи: 802.11n, частота 2.4 ГГц...
→ Оставить отзыв
Для начала давайте определим что такое IPTV и мини-роутер. Мини-роутер (маршрутизатор) – сетевое...
→ Оставить отзыв
Подключение При подключении нового роутера к сети интернет необходимо подключить кабель провайдера...
→ Оставить отзыв
Сначала – посмотрим, что такое Wi-Fi 3G роутер вообще, и чем такие решения лучше «модемов». В...
→ Оставить отзыв