6.2. Поиск кратчайших путей между каждой парой вершин графа

В разд. 6.1 были рассмотрены алгоритмы нахождения кратчайших путей в графе из начальной вершины до конечной вершины или до всех других вершин (алгоритмы Дейкстры и Форда). Теперь рассмотрим задачу поиска кратчайших путей между каждой парой вершин. Решить её можно, применив рассмотренные в разд. 6.1 алгоритмы для каждой вершины, то есть в качестве начальной брать по очереди все вершины графа и находить кратчайшие пути из начальной вершины до всех других вершин. Такой подход для графа G=(V,E) с неотрицательными весами дуг дал бы алгоритм с трудоемкостью О(|V|³). В случае графов с отрицательными весами дуг трудоемкость резко возрастает. Однако для нахождения кратчайших путей между каждой парой вершин существует более общий метод (алгоритм Флойда), требующий О(|V|³) операций даже для графов с отрицательными весами дуг.

Пусть W=║w_ij║- матрица весов графа G=(V,E), и мы хотим вычислить матрицу W^*=║w_ij^*║, в которой w_ij^* - длина кратчайшего пути из iV в jV.

Аналогично методу вычисления транзитивного замыкания (разд. 5.4) можно вычислить матрицу W^*, определив последовательность матриц W⁽⁰⁾=║w_ij⁽⁰⁾║, W⁽¹⁾=║w_ij⁽¹⁾║,, W^(|V|)=║w_ij^(|V|)║, следующим образом:

1. w_ij⁽⁰⁾=w_ij;

2. w_ij^(k)=min{w_ij^(k-1),w_ik^(k-1)+w_kj^(k-1)}. (6.2)

Утверждение: Значение w_ij^(k) есть длина кратчайшего пути из вершины iV в вершину jV с промежуточными вершинами, принадлежащими множеству {1,2,,k}V. Тогда W^(|V|) – матрица кратчайших путей, а элемент матрицы w_ij равен длине кратчайшего пути из вершины i в вершину j.

Доказательство данного утверждения проводится методом математической индукции, аналогично доказательству утверждения в разд.5.4.

Алгоритм 4. Алгоритм Флойда

Алгоритм следует из выражения 6.2

for k = 1 to |V| do

for i = 1 to |V| do

for j = 1 to |V| do

w_ijmin{w_ij,w_ik+w_kj}

Заметим, что на алгоритм отрицательность весов не влияет, но если в графе имеется контур отрицательной длины, то алгоритм не работает. Также отметим, что данный алгоритм является более эффективным для вычисления единственного кратчайшего пути в плотном орграфе, чем алгоритм Форда.

Упражнения:

1. Как и при реализации алгоритма нахождения транзитивного замыкания (алгоритм 2, разд.5.4), в алгоритме 4 элементы (k-1)-ой матрицы непосредственно преобразуются в элементы матрицыk-ой матрицы. Докажите корректность такой реализации.

2. Алгоритм 4 вычисляет только длины кратчайших путей между каждой парой вершин. Доработайте алгоритм таким образом, чтобы сохранялась информация о самих кратчайших путях (см. разд.5.4, упр.4).

7. Потоки

Поток определяет способ пересылки некоторых объектов из одного пункта в другой. Потоки, например, возникают при транспортировке товаров, при движении людей и транспорта и так далее.

Применительно к графам поток задает способ пересылки некоторых объектов (единиц потока) из одной вершины графа (из источника) в другую вершину (сток) по дугам в направлении их ориентации. Максимальное число единиц потока, которые могут проходить по дуге, называют пропускной способностью дуги. Кроме пропускной способности дуг в некоторых задачах задают стоимость прохождения единицы потока по дугам.

В данной главе будут рассмотрены алгоритмы поиска максимального потока и поиска потока минимальной стоимости. Также в данной главе рассматриваются подходы к решению задач 1 и 2, сформулированных во введении к данному пособию.