3.4 Контрольный пример
Допустим, имеется некоторый граф G (рисунок 11).
Рисунок 11
Найдем для всех пар его вершин кратчайшие пути, используя алгоритм Флойда.
Построим матрицы D и P для начального состояния графа.
Рисунок 12 - Начальное состояние
Шаг 2.
Рис. 13. Матрицы D и P
Шаг 3.
Рис. 14. Матрицы D и P
Шаг 3
Рисунок 15 - Матрицы D и P
Шаг 4
Рисунок 16 - Матрицы D и P
Конечные матрицы D4 и P4 содержат всю информацию, необходимую для определения кратчайших путей между любыми двумя вершинами. Например, кратчайшее расстояние между вершинами 1 и 5 равно d = 12.
Для нахождения соответствующих маршрутов напомним, что сегмент маршрута (i, j) состоит из ребра (i, j) только в том случае, когда P = j. В противном случае узлы i и j связаны, по крайней мере, через один промежуточный узел. Например, поскольку S= 4 и S = 5, сначала кратчайший маршрут между узлами 1 и 5 будет иметь вид 1->4->5. Но так как S не равно 4, узлы 1 и 4 в определенном пути не связаны одним ребром (но в исходной сети они могут быть связаны непосредственно). Далее следует определить промежуточный узел (узлы) между первым и четвертым узлами. Имеем S = 2 и S = 4, поэтому маршрут 1->4 заменяем 1->2->4. Поскольку S = 2 и S = 4, других промежуточных узлов нет. Комбинируя определенные сегменты маршрута, окончательно получаем следующий кратчайший путь от узла 1 до узла 5: 1->2->4->5. Длина этого пути равна 12.
Теперь найдем кратчайшие пути, используя программу, разработанную при выполнении данной курсовой работы.
- Введение
- 1. Анализ предметной области
- 1.1 Основные определения
- 1.2 Компьютерные средства для реализации задачи
- 1.3 Цель и задачи курсовой работы
- 2. Анализ задачи и методов ее решения
- 2.1 Задача поиска выделенного кратчайшего пути
- 2.2 Алгоритм Дейкстры
- 2.3 Задача поиска всех кратчайших путей
- 2.4 Алгоритм Флойда
- 3. Разработка программы
- 3.1 Характеристика программы и системные требования
- 3.2 Описание модульной структуры разработанной программы
- 3.3 Описание диалога с пользователем
- 3.4 Контрольный пример
- Заключение
- Нахождение кратчайшего пути (алгоритмы Флойда и Дийкстра).
- 3.5. Путь минимального веса в графе. Алгоритм Флойда
- Алгоритм Флойда (кратчайшие пути между всеми парами вершин)
- 2.4. Алгоритм Флойда (кратчайшие пути между всеми парами вершин)
- 6.2. Поиск кратчайших путей между каждой парой вершин графа
- 2.3 .Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин (алгоритм Флойда).
- Нахождение кратчайших путей между парами вершин
- Алгоритм Флойда определения кратчайших путей между всеми парами вершин графа
- 3.2. Кратчайшие пути между всеми парами вершин