Введение. 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 год).

Примечаний нет.