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

Цель: научить находить кратчайшие цепи в графе при помощи алгоритма Флойда.

Оборудование: практикум, тетрадь для лабораторных и практических работ.

Литература:

1. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1979. С. 189-191.
2. Новиков Ф. А. Дискретная математика для программистов. - СПб.: Питер, 2000. С. 228-232.
3. Таха, Хемди. Введение в исследование операций - М.: Издательский дом "Вильямс", 2005. С. 250-265.

Время выполнения: 2 часа.

ВОПРОСЫ ВХОДНОГО КОНТРОЛЯ:

1. Дайте определение графа, приведите примеры.
2. Сформулируйте определение пути (маршрута).
3. Дайте понятие кратчайшего пути.
4. Сформулируйте постановку задачи нахождения кратчайшего пути от заданного узла до всех остальных узлов в графе.
5. Объясните суть алгоритма Флойда.

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ:

Алгоритм Флойда находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i, j) равен расстоянию d_ij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.
Основная идея метода Флойда: пусть есть три узла i, j и k и заданы расстояния между ними. Если выполняется неравенство d_ij + d_jk < d_ik, то целесообразно заменить путь i → k путем i → j → k. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

Алгоритм Флойда

1) Определяем начальную матрицу расстояний D₀ и матрицу последовательности узлов S₀. Диагональные элементы обеих матриц помечаются знаком "-", показывающим, что эти элементы в вычислениях не участвуют. Полагаем k = 1;

2) Задаем строку k и столбец k как разрешающую строку и разрешающий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам d_ij матрицы D_k-1. Если выполняется неравенство

d_ik + d_kj < d_ij (i ≠ k, j ≠ k, i ≠ j),

то делаем следующее:

a) создаем матрицу D_k путем замены в матрице D_k-1 элемента d_ij суммой d_ik + d_kj,

b) создаем матрицу S_k, меняя в матрице S_k-1 элемент s_ij на k.

3) Полагаем k = k + 1, повторяем этап 2 до тех пор, пока выполняется условие k ≤ n.

4) После реализации n этапов алгоритма определение по матрицам D_n и S_n кратчайшего пути между узлами i и j выполняется по следующим правилам:

а) расстояние между узлами i и j равно элементу d_ij в матрице D_n;

б) промежуточные узлы пути от узла i к узлу j определяем по матрице S_n. Пусть s_ij = k, тогда имеем путь i → k → j. Если далее s_ik = k и s_kj = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ:

Найти кратчайшие пути между всеми парами вершин графа

СОДЕРЖАНИЕ РАБОТЫ:

ВОПРОСЫ ВЫХОДНОГО КОНТРОЛЯ:

1. Дайте определение графа, приведите примеры.
2. Сформулируйте определение пути (маршрута).
3. Дайте понятие кратчайшего пути.
4. Сформулируйте постановку задачи нахождения кратчайшего пути от заданного узла до всех остальных узлов в графе.
5. Объясните суть алгоритма Флойда.

ДОМАШНЕЕ ЗАДАНИЕ:

Выучить алгоритм Флойда.