Поиск кратчайшего пути между парами вершин в ориентированном и неориентированном графах путем использования алгоритма Флойда
2.4 Алгоритм Флойда
Алгоритм Флойда - это алгоритм поиска кратчайших путей между всеми вершинами графа.
Пусть дан взвешенный орграф с n вершинами и матрицей весов W. Каждый элемент матрицы весов w равен весу дуги <x, x> (если такой дуги нет, то w), а w=0 .
Предположим, что граф не содержит контуров отрицательной длины. Пронумеруем вершины графа от 1 до n. Обозначим W матрицу с элементами w, каждый из которых равен длине кратчайшего пути из вершины i в вершину j, который может содержать в качестве промежуточных вершин только первые k вершин графа. Если такого пути не существует, то w=. W=W. По матрице W вычисляется матрица W, содержащая кратчайшие пути между всеми вершинами графа. Элементы матрицы W на k-й итерации вычисляются следующим образом:
w=min, (2)
где w-длина кратчайшего пути из вершины i в вершину k, в которой в качестве промежуточных используются первые k-1 вершины графа.
Для того, чтобы по окончании работы алгоритма можно было быстро построить кратчайший путь, на каждой итерации вместе с матрицей Wстроится матрица P, каждый элемент которой p равен номеру вершины, предшествующей вершине j в текущем ij пути.
На текущей итерации
p, и (3)
p= (4)
Номера вершин, включаемых в кратчайший путь, определяются следующим образом: и т.д.
Основные шаги алгоритма:
1. Пронумеровать вершины графа целыми числами k=0. Определить матрицу W. Определить матрицу P, p=i, , i,j=1. n и p=0, =1. n.
2. Если k=n, работа алгоритма закончена (W-эта матрица весов кратчайших путей между всеми парами вершин графа, определяемых с помощью матрицы P). Если kn, то k=k+1, переход к шагу 3.
3. Вычислить для всех i,j=1…n элементы w=min. Если < , то p=p. Иначе p.
4. Если для некоторого 1 элемент с , то в графе имеется контур отрицательной длины и работа алгоритма завершается. Иначе перейти к шагу 2. [1]