Дискретная математика: Учебное пособие. Часть 3 - Основы теории графов, страница 16

хp        li,p                               lp,j   xj                 li,j                                       xj

В основе всех алгоритмов лежит операция сравнения двух простых маршрутов. На рис. 30 показаны два простых маршрута, соединяющих вершины х_i и х_j. Выбор кратчайшего пути между вершинами х_i и х_j есть результат сравнения длин двух маршрутов, т.е. L_i,j=min{l_i,j; (l_i,p+ l_p,j)}. Если существует несколько вершин, смежных с вершинами х_i и х_j следует выполнять процедуру последовательно, сравнивая длины двух Рис. 30 Сравнение маршрутов.       маршрутов для каждой вершины.

Алгоритм Флойда. Для того, чтобы выбирать  кратчайшие путь и переходы между вершинами x_i и x_j, необходимо использовать две матрицы: матрицу кратчайших путей ║l(n;n)║ и матрицу кратчайших переходов ║n(n;n)║, которые позволяют вычислять и сравнивать различные маршруты через базовую вершину графа.

Вершина х_p в матрице кратчайших путей называется базовой, а строка и столбец матрицы ║l^p║ - базовыми (выделены в матрице заливкой), если она позволяет сравнивать кратчайшие пути между любой парой вершин x_i и x_j, смежных с вершиной х_p. Базовая вершина позволяет найти путь из вершины x_i в вершину x_j через вершину x_p по формуле l_ij=(l_ip+ l_pj), представить этот результат для сравнения с имеющимся значением l_ij и выбрать кратчайший путь. Если в качестве базовой, использовать последовательно все вершины, начиная с вершины х₀,

то за p=(n-1) шагов итерации можно найти кратчайшие пути между любой парой вершин. Для p=0 матрица ║l⁰║ есть матрица весов графа.

Матрица переходов n^p производна относительно матрицы кратчайших путей. Для p=0 элементы матрицы n⁰ есть концевые вершины перехода из х_i в х_j. Поэтому в каждом столбце х_j матрицы n⁰ указана вершина х_j. Результатом p-го шага итерации происходит замена вершины перехода вершиной кратчайшего перехода по формулам:

а) если (l_i,p+ l_p,j)^p³l_i,j^p, то n_i,j ^(p+1)= n_i,j ^p=х_j;

б) если (l_i,p+ l_p,j)^p<l_i,j^p, то n_i,j ^(p+1)=х_p.

Следовательно, для анализа n-вершинного графа необходимо последовательно построить n матриц кратчайших путей и кратчайших переходов.

Итак, по алгоритму Флойда:

шаг 1: составить таблицы: матрицу весов ║l^p║ и матрицу переходов ║n^p║ для p=0, где p – шаг итерации;

шаг 2: определить вершину p базовой и выделить базовые строки и столбец;

шаг 3: вычеркнуть строки и столбцы, базовые элементы которых имеют значение ¥, т.к. (l_i,p+¥) и (¥+ l_p,j) всегда больше конечного значения l_i,j;