Практическое занятие 4 Тема: поиск оптимальных путей с использованием алгоритма Флойда Контрольные вопросы

1. Сущность матричного алгоритма Флойда – поиска оптимальных путей.

2. Сущность дистанционной матрицы D и её формирование.

3. Сущность маршрутной матрицы Г и её формирование.

4. Механизм построения элементов матриц Д и Г.

4. Сколько необходимо выполнить итераций для получения оптима-льного решения.

5. Сфера использования алгоритма Флойда.

Алгоритм Флойда предоставляет возможность получить как матрицу длин кратчайших расстояний L_опт = D, так и маршрутную матрицу, которая определяет вершины ( ветви) графа, которые составляют пути.

Алгоритм Флойда работает таким образом. Сначала за длину кратчайшего пути между произвольными вершинами i и j принимается длина ветви lij, которая объединяет эти вершины. Потом последовательно проверяются все промежуточные вершины, расположенные между i и j. Если длина пути, которая проходит через определенную промежуточную вершину k, меньше предыдущего (текущего) значения, которое было обозначено, например, dij, то переменной dij присваивается новое значение. Заметим, что исходное значение dij = lij. Данная процедура повторяется для всех пар вершин, пока не будут полученны все значения матрицы L_опт = D.

Для любых трех разных вершин – i, k и j – сформулированные условия могут быть записаны в виде неравенства, поскольку в противном случае

dik + dkj dij (i k j), (4.1)

кратчайший путь из вершины і к вершине j должен содержать вершину k и тогда величина dij не была бы равной длине кратчайшего пути. Рис.4.1 иллюстрирует выполнение процедуры сравнения (4.1) для пары вершин і и j.

Рисунок 4.1 – Пример поиска длины кратчайшего пути

Обозначим символом оценку длины кратчайшего пути из і в j, полученную на q–ой итерации.

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

Способ получения на q–й итерации величины может быть описано с помощью следующей трехместной операции (операции треугольника):

(4.2)

Если операцию (4.1) выполнять с данной парой вершин i и j и всеми вершинами k (i k j) в порядке возрастания номеров k, то значение полученное на последней итерации, будет равняться длине кратчайшего пути из вершины i в вершину j.

На каждой итерации алгоритма строится две матрицы.

Первая из них, называемая матрицей длин кратчайших путей, содержит текущие оценки длин кратчайших путей, то есть на q–й итерации данная матрица определяется как .

Алгоритм начинает работу при . Затем, выполняя трехместную операцию (4.2) со всеми элементами матрицы D⁰, получаем D¹ и до тех пор, пока для каждой пары вершин не будет выполнен критерий оптимальности (4.1).

Вторая матрица, называемая матрицей маршрутов (обозначим ее Г), служит для нахождения промежуточных вершин (если такие имеются) кратчайших путей. На q–й итерации она определяется как , где – первая промежуточная вершина кратчайшего пути из i в j, выбираемая из вершин множества {1, 2, ..., k} (i k j). Алгоритм начинает работу, за , где . На q–й итерации вершина может быть получена из соотношения

После построения матриц D⁰ и Г⁰ нужно для каждого k = 1, 2, .. п, используя для вычислений элементы матрицы , полученной на

(q-1) –й итерации, выполнить следующую процедуру.

Шаг 1. Вычеркнуть элементы k-й строки и k-го столбца. Назовем эти множества элементов базовой строкой и базовым столбцом.

Шаг 2. Для каждого элемента (i k) матрицы , начиная с первого, расположенного в левому верхнему углу матрицы, проверить выполнение неравенства:

(4.3)

Если неравенство (4.2) выполняется, то нужно выбрать новые значения i и j, и снова выполнить шаг 2. Если неравенство (4.2) не выполняется, то элементу , матрицы Dq нужно присвоить значение , а элементу матрицы Г_q – присвоить значение .

После проверки неравенства (4.2) для всех элементов (i, j) нужно снова перейти к выполнению шага 1 при q = q+1 до q=n. В соответствии с (4.2), при получении D^q из D^q-1 трехместную операцию, которая позволяет установить факт принадлежности базового узла k к кратчайшему пути, следует выполнять только с элементами матрицы D^q-1 , не принадлежащими ни базовой строке, ни базовому столбцу.

Для иллюстрации работы алгоритма Флойда определим кратчайшие пути между всеми парами вершин графа, изображенного на рис. 4.2.

Начальные значения элементов матрицы D⁰ добавлено в табл. 4.1, матрицы Г⁰ – в табл. 4.2.

Рисунок 4.2 – Пример графа относительно использования алгоритма Флойда

Таблица 4.1 Таблица 4.2

Итерация 1. Вершина k = 1 определяется как базовая, ведь в матрице D0 вычеркиваем первую строку и первый столбец. Поскольку в базовой строке в столбцах 3, 5, 6, 7, 8 содержатся элементы, равные , то элементы этих столбцов можно не исследовать в соответствии с выражением (4.2).

	1	2	3	4	5	6	7	8
1		9		3					Базовая строка
2	9	0
3
4	3			0
5
6
7
8
Базовый столбец

Рисунок 4.3 – Пример относительно итерации 1

В базовом первом столбце в строках 3, 5, 6, 7, 8 содержатся элементы, равные , поэтому, согласно (4.2), элементы этих строк можно не исследовать. Для того, чтобы определить, приведет ли использование вершины 1 к более коротким путям, чем те, которые записаны в D⁰, нужно исследовать с помощью трехместной операции (4.2) лишь элементы матрицы D⁰, изображенные на рис. 4.3, а именно элементы . Но поскольку элементы главной диагонали (i= j) можно не рассматривать, применение операции (4.1) дает следующие результаты:

Поскольку

и

Поэтому указанные элементы размещаются в матрицу D¹, остальные элементы матрицы D⁰ переносятся в D¹ без изменения. Элементы матрицы Г¹ при этом: и , остальные элементы Г¹ равны соответствующим элементам матрицы Г⁰.

Матрицы D¹ и Г¹ представлены в табл.. 4.3 и 4.4 соответственно.

Таблица 4.3. Таблица 4.4

Итерация 2. Определяем вершину 2 как базовую и вычеркиваем в матрице D¹ вторую строку и второй столбец. Поскольку во второй строке в столбцах 6, 7 и 8 есть , соответствующие строки не рассматриваются. Кроме того, не рассматриваются элементы главной диагонали. В результате необходимо исследовать элементы:

Новые оценки получают лишь такие элементы:

Следовательно, .

Матрицы D² и Г² показаны в табл. 4.5 и 4.6.

Таблица 4.5 Таблица 4.6

Выполняя аналогичные вычисления на итерациях 3, 4, 5, 6, 7, 8, получим результат – матрицы D и Г. Решение, полученное на итерации 5, не улучшается на последующих итерациях. Следовательно, оптимальное решение:

D = D⁵, Г = Г⁵.

Матрицы D и Г представлены в таблицах 4.7 и 4.8.

Таблица 4.7 Таблица 4.8

Пусть необходимо определить кратчайший путь d_15. Длина пути . Для нахождения соответствующей последовательности вершин, которые составляют путь, обратимся к матрице Г⁵. Поскольку , то вершина 4 является первой промежуточной в кратчайшем пути из вершины 1 к вершине 5. Затем отыскиваем следующую вершину на пути к вершине 5, обращаясь к элементу γ₄₅ = 3, далее γ₃₅ = 5. Следовательно, последовательность вершин пути μ₁₅ определена:

μ₁₅ = {1, 4, 3, 5}.

Аналогично определяются другие кратчайшие пути. Например, длина пути μ₈₂ = d₈₂ = 15, путь состоит из вершин:

μ₈₂ = {8, 5, 3, 2}.