microbik.ru
1

московский институт электроники и математики

Расчетно-графическая работа №3

«Расчет оптимальных маршрутов в сети»




Выполнил: Алексашенков Д.В. С-94

17.12.2009

Проверил: Леохин Ю.Л.




Оглавление


Задание 3

Алгоритмы 4

Беллман-Форд 4

Дейкстра 4

Решение 5

Метод Беллмана-Форда 5

Метод Дейкстры 6


Задание


Исходные данные: оптимальные маршруты определяет маршрутизатор M4.

  1. Найти оптимальные маршруты, ведущие ко всем маршрутизаторам сети методом Беллмана-Форда.

  2. Найти оптимальные маршруты, ведущие ко всем маршрутизаторам сети методом Дейкстры.


Алгоритмы

Беллман-Форд


Для нахождения оптимального маршрута между двумя точками графа необходимо:

  1. Найти все возможные маршруты, количество рёбер в которых может быть [0; n - 1], где и n – это количество вершин графа.

  2. Для каждого маршрута рассчитать его метрику, т.е. Количество хопов до маршрутизатора.

  3. Выбрать из полученного множества минимальный вес. Маршрут, соответствующий этому минимальному весу будет оптимальным.

Дейкстра


Для нахождения оптимального маршрута между исходной точкой и всеми остальными точками графа необходимо:

  1. Инициализация: Метка исходной вершины полагается равной 0, метки остальных вершин — бесконечности. Все вершины графа помечаются как непосещённые.

  2. Шаг алгоритма: Если все вершины посещены, алгоритм завершается. В противном случае из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Вершины, соединённые с вершиной u рёбрами, называются соседями этой вершины. Для каждого соседа рассматривается новая длина пути, равная сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, метка заменяется этой длиной. Рассмотрев всех соседей, вершина u помечается как посещённая, и шаг повторяется.


Решение

Метод Беллмана-Форда


Поиск

Путь

Метрика

4 – 1

4 – 3 – 2 – 1

3

4 – 2

4 – 3 – 2

2

4 – 3

4 – 3

1

4 – 4

4

0

4 – 5

4 – 5

1

4 – 6

4 – 5 – 14 – 6

3

4 – 7

4 – 5 – 14 – 7

3

4 – 8

4 – 13 – 12 – 9 – 8

4

4 – 9

4 – 13 – 12 – 9

3

4 – 10

4 – 13 – 12 – 9 – 10

4

4 – 11

4 – 13 – 12 – 11

3

4 – 12

4 – 13 – 12

2

4 – 13

4 – 13

1

4 – 14

4 – 5 – 14

2

4 – 15

4 – 15

1


Метод Дейкстры


Поиск

Путь

Вес

4 – 1

4 – 3 – 2 – 1

7

4 – 2

4 – 3 – 2

3

4 – 3

4 – 3

2

4 – 4

4

0

4 – 5

4 – 5

4

4 – 6

4 – 5 – 14 – 6

8

4 – 7

4 – 5 – 14 – 7

8

4 – 8

4 – 13 – 12 – 9 – 8

8

4 – 9

4 – 13 – 12 – 9

6

4 – 10

4 – 13 – 12 – 9 – 10

7

4 – 11

4 – 13 – 12 – 11

5

4 – 12

4 – 13 – 12

4

4 – 13

4 – 13

3

4 – 14

4 – 5 – 14

5

4– 15

4 – 15

1