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

                   хp

       li,p                               lp,j

 


xj                 li,j                                       xj

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

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

Вершина хp в матрице кратчайших путей называется базовой, а строка и столбец матрицы ║lp║ - базовыми (выделены в матрице заливкой), если она позволяет сравнивать кратчайшие пути между любой парой вершин xi и xj, смежных с вершиной хp. Базовая вершина позволяет найти путь из вершины xi в вершину xj через вершину xp по формуле lij=(lip+ lpj), представить этот результат для сравнения с имеющимся значением lij и выбрать кратчайший путь. Если в качестве базовой, использовать последовательно все вершины, начиная с вершины х0,

np

x0

..

xi

xp

xj

..

xn

x0

x0

..

xi

xp

xj

..

xn

..

x0

..

xi

xp

xj

..

xn

xi

x0

..

xi

xp

xj

..

xn

xp

x0

..

xi

xp

xj

..

xn

xj

x0

..

xi

xp

xj

..

xn

..

x0

..

xi

xp

xj

..

xn

xn

x0

..

xi

xp

xj

..

xn

lp

x0

..

xi

xp

xj

..

xn

x0

0

..

l0i

l0j

..

l0n

..

..

0

..

..

..

..

..

xi

li0

..

0

lip

lij

..

lin

xp

..

lpi

0

lpj

..

lpn

xj

lj0

..

lji

ljp

0

..

ljn

..

..

..

..

..

..

0

..

xn

ln0

..

lni

lnp

lnj

..

0nn

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

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

а) если (li,p+ lp,j)p³li,jp, то ni,j (p+1)= ni,j pj;

б) если (li,p+ lp,j)p<li,jp, то ni,j (p+1)p.

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

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

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

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

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