Поиск кратчайшего пути между парами вершин в ориентированном и неориентированном графах путем использования алгоритма Флойда

курсовая работа

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.

Теперь найдем кратчайшие пути, используя программу, разработанную при выполнении данной курсовой работы.

Делись добром ;)