7.4 Нахождение кратчайших путей между парами вершин

Пусть дан орграф G=(V, E)и необходимо определить кратчайшие пути между всеми парами вершин орграфа. Каждой дугеэтого графа сопоставлена неотрицательная стоимостьC[v, w]. Общая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин (v, w) любого пути от вершиныvв вершиныw, длина которого минимальна среди всех возможных путей отvкw.

Для решения поставленной задачи применим алгоритм Флойда. Для этого пронумерует вершины графа последовательно от 1 до n.

Алгоритм Флойда использует матрицу Аразмерав которой вычисляются длины кратчайших путей. ВначалеА[i, j]= C[i, j]для всех i ≠ j.Если дугаотсутствует, тоC[i, j]=∞. Каждый диагональный элемент матрицыАравен 0.

Над матрицей Авыполняетсяnитераций. Послек-ой итерацииА[i, j] содержит значение наименьшей длины путей из вершиныi в вершину j, которые не проходят через вершины с номером, большимк, т.е. между концевыми вершинами пути изi вj могут находиться только вершины, номера которых меньше или равнык. На к-ой итерации для вычисления матрицы А применяется следующая формула:

Нижний индекс кобозначает значение матрицыАпослек-ой итерации. Графическая интерпретация приведенной формулы показана на рис. 7.5.

Рис. 7.5 – Включение вершины кв путь от вершиныiк вершинеj

Для вычисления проводится сравнение величиныс величиной. Если путь через вершинукдешевле, чем, то величинаизменяется.

На рис. 7.6 приведен помеченный орграф, а на рис. 7.7 – значения матрицы А после трех итераций.

Рис. 7.6 – Помеченный орграф

Рис. 7.7 – Последовательные значения матрицы А

Равенства иозначает, что нак-ой итерации элементы матрицыА, стоящие вк-ой строке ик-ом столбце, не изменяются. Процедура, реализующая алгоритм Флойда, представлена ниже.

For i:=1 to n do

For j:=1 to n do

readln(C[i,j]);

For i:=1 to n do

For j:=1 to n do

A[i,j]:=C[i,j];

For i:=1 to n do

A[i,i]:=0;

For k:=1 to n do

For i:=1 to n do

For j:=1 to n do

if A[i,k]+ A[k,j]< A[i,j] then

A[i,j]:= A[i,k]+ A[k,j];

End.

Время выполнения этой программы имеет порядок. Поскольку алгоритм Дейкстры с использованием матрицы смежности находит кратчайшие пути от одной вершины за время порядка, то в случае применения алгоритма Дейкстры для нахождения всех кратчайших путей потребует времени порядка, т.е. получается такой же временной порядок, как и в алгоритме Флойда. Еслиe, количество дуг в орграфе, значительно меньше, чем, то рекомендуют применять алгоритм Дейкстры со списками смежности. Тогда время нахождения кратчайших путей имеет порядокчто значительно луче алгоритма Флойда, хотя бы для больших разреженных графов.

7.5 Нахождение центра ориентированного графа

Определим понятиецентральной вершины орграфа. Пустьv- произвольная вершина орграфаG=(V, E). Эксцентриситет (максимальное удаление) вершиныvопределяется какmax{минимальная длина пути от вершины w до вершины v }.

Центром орграфа Gназывается вершина с минимальным эксцентриситетом, т.е. это вершина, для которой максимальное расстояние (длина пути) до других вершин минимально.

Рассмотрим помеченный орграф, показанный на рис. 7.8.

Рис. 7.8 – Помеченный орграф

В этом графе вершины имеют следующие эксцентриситеты.

Откуда видно, что центром данного орграфа является вершина d.

Пусть С– матрица стоимостей для орграфаG. Тогда центр орграфа можно найти, применив следующий алгоритм.

1. Применить алгоритм Флойда к матрице С для вычисления матрицыА, содержащей все кратчайшие пути орграфаG.

2. Найти максимальное значение в каждом столбце iматрицыА. Это значение равно эксцентриситету вершиныi.

3. Найти вершину с минимальным эксцентриситетом. Она и будет центром графа G.

Матрица всех кратчайших путей для орграфа из рис. 7.8 представлена на рис. 7.9. Максимальные значения в каждом столбце приведены под матрицей.

Рис. 7.9 – Матрица кратчайших путей