Введение. 4
Задание. 6
Исходные данные: оптимальные маршруты определяет маршрутизатор M10.
1. Найти оптимальные маршруты, ведущие ко всем маршрутизаторам сети, методом Беллмана-Форда.
2. Найти оптимальные маршруты, ведущие ко всем маршрутизаторам сети, методом Дейкстры.
Решение. 7
Приложение. 12
Используемая литература. 15
|
Аннотация.
В работе выполняется расчет оптимальных маршрутов в сети, состоящей из пятнадцати маршрутизаторов, методами Беллмана-Форда и Дейкстры.
Алгори?тм Де?йкстры - алгоритм на графах, изобретенный Э. Дейкстрой. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием кратчайший путь - первый (Shortest Path First).
Пусть дан простой взвешенный граф G(V,E) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа. Каждой вершине из V сопоставляется метка - минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово - на каждом шаге он "посещает" одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены. Метка самой вершины a полагается равной 0, метки остальных вершин - бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные. Если все вершины посещены, алгоритм завершается. В противном случае из еще не посещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.
Алгоритм Беллмана - Форда - алгоритм поиска кратчайшего пути во взвешенном графе. Алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана - Форда допускает рёбра с отрицательным весом.
Дан ориентированный или неориентированный граф G со взвешенными рёбрами. Длиной пути назовём сумму весов рёбер, входящих в этот путь. Требуется найти кратчайшие пути от выделенной вершины s до всех вершин графа.
Так выглядит алгоритм поиска длин кратчайших путей в графе без отрицательных циклов:
for vЄV
do d[v]?+?
d[s]?0
for I?1 to |V|-1
do for (u,v) ЄE
if d[v]>d[u]+w(u,v)
then d[v]?d[u]+w(u,v)
return d
Здесь V - множество вершин графа G, E - множество его рёбер, а w - весовая функция, заданная на ребрах графа. Внешний цикл выполняется |V| - 1 раз, поскольку кратчайший путь не может содержать большее число ребер, иначе он будет содержать цикл, который точно можно выкинуть.
|
1. В. Г. Олифер, Н. А. Олифер, "Компьютерные сети. Принципы, технологии, потоколы", 3-е издание, изд. Питер, 2006 год).
|