Московский государственный институт электроники и математики
(технический университет)
Кафедра «Информационно-коммуникационные технологии»
Задача № 3
по дисциплине
«Технические средства сетей ЭВМ»
на тему
«Расчёт оптимальных маршрутов в сети»
Выполнил: Группа: Проверил: |
С-94 |
Москва 2011 г.
2. Задание.
Оптимальные маршруты определяет маршрутизатор М14
3. Алгоритм.
3.1. Беллман-Форд.
Для нахождения оптимального маршрута между двумя точками графа необходимо:
Найти все возможные маршруты, количество рёбер в которых может быть [0; n - 1], где
и n – это количество вершин графа. Для каждого маршрута рассчитать его метрику, т. е. Количество хопов до маршрутизатора. Выбрать из полученного множества минимальный вес. Маршрут, соответствующий этому минимальному весу будет оптимальным. 3.2. Дейкстра.
Для нахождения оптимального маршрута между исходной точкой и всеми остальными точками графа необходимо:
Инициализация: Метка исходной вершины полагается равной 0, метки остальных вершин — бесконечности. Все вершины графа помечаются как не посещённые. Шаг алгоритма: Если все вершины посещены, алгоритм завершается. В противном случае из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Вершины, соединённые с вершиной u рёбрами, называются соседями этой вершины. Для каждого соседа рассматривается новая длина пути, равная сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, метка заменяется этой длиной. Рассмотрев всех соседей, вершина u помечается как посещённая, и шаг повторяется.4. Решение.
4.1. Беллман-Форд.
Поиск:
Путь:
Метрика: 3
Поиск:
Путь:
Метрика: 3
Поиск:
Путь:
Метрика: 3
Поиск:
Путь:
Метрика: 2
Поиск:
Путь:
Метрика: 1
Поиск:
Путь:
Метрика: 1
Поиск:
Путь:
Метрика: 3
Поиск:
Путь:
Метрика: 8
Поиск:
Путь:
Метрика: 2
Поиск:
Путь:
Метрика: 2
Поиск:
Путь:
Метрика: 2
Поиск:
Путь:
Метрика: 2
Поиск:
Путь:
Метрика: 1
Поиск:
Путь: 14 –
Метрика: 2
4.2. Дейкстра.
Поиск:
Путь:
Вес: 8
Поиск:
Путь:2 (1) 2
Вес: 7
Поиск:
Путь:(2) 3
Вес: 7
Поиск:
Путь:
Вес: 5
Поиск:
Путь:
Вес: 1
Поиск:
Путь:
Вес: 3
Поиск:
Путь:
Вес: 2
Поиск:
Путь:
Вес: 1
Поиск:
Путь:
Вес: 3
Поиск:
Путь:(2) 10
Вес: 5
Поиск:
Путь:(2) 11
Вес: 5
Поиск:
Путь:
Вес: 4
Поиск:
Путь:(1) 15
Вес: 6
