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

В разд. 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).

ПОТОКИ

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

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

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