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

курсовая работа

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]

Делись добром ;)