8.8 Нахождение кратчайших путей в графе

Будем рассматривать ориентированные графы G = <V, Е>, дугам которых приписаны веса. Это означает, что каждой дуге (u, v)eE поставлено в соответствие некоторое вещественное число a(u, v), называемое весом данной дуги. Полагаем, что a(u, v)=oo, если не существует дуга (u, v). Если последовательность вершин

Р Vq , Vj,..., V определяет путь в графе G, то его длина определяется как сумма /^ G\ V₂-_j, V_i). Нас будет

i=\ интересовать нахождение кратчайшего пути между двумя фиксированными вершинами s, t eV. Длину такого пути обозначим d(s, t) и назовем расстоянием от s до t (расстояние, определенное таким образом, может быть и отрицательным). Если не существует ни одного пути из s в t, то полагаем d(s, t) =оо. Отметим, что если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем.

Практическая интерпретация:

1. вершины - города, дуги - пути между городами, длины которых представлены весами. Ищем кратчай­шие пути между городами;

2. вес дуги - стоимость (или время) передачи информации между вершинами. Тогда ищем самый дешевый (или самый скорый) путь передачи информации.

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

Действительно, для произвольных s, t eV (s^t) существует вершина v такая, что

d(s, t) = d(s, v) + d(v, t).

Таким свойством обладают предпоследние вершины кратчайшего пути из s в t. Далее мы можем найти вершину и, для которой d(s, v) = d(s, u) + d(u, v) и т.д. Из условия положительности длины всех контуров следу­ет, что последовательность t, v, u, ... не содержит повторений и заканчивается вершиной s. Перечислив верши­ны в обратном порядке, найдем кратчайший путь из s в t.

Алгоритм для нахождения кратчайшего пути можно построить с использованием стека, куда последова­ тельно заносим вершины t, v, u, ..., s:

1 BEGIN

2. СТЕК := 0; СТЕК <^ t; v := t;

3. WHILE v^s DO

4. BEGIN

5. u := вершина, для которой d[v] = d[u] + a[u, v]

6. СТЕК <t= u;

7. v := u

8 END

9 END

Отметим, что если выбор вершины и в строке 5 происходит в результате просмотра всех вершин, то слож­ность нашего алгоритма - 0(п²). Если же будем просматривать только список ПРЕДШу], содержащий все вершины и, такие, что u—>v, то сложность будет О(т).

8.9 Кратчайшие пути от фиксированной вершины

Суть большинства алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t со­стоит в следующем.

При данной матрице весов дуг a[u, v], u, ve V, вычисляем некоторые верхние ограничения d[v] на расстоя­ния от вершины s до всех v е V.

Каждый раз, когда окажется, что D[u]+a[u, v]<D[v] (1), оценку D[v] улучшаем: D[v] := D[u]+a[u, v]. Про­цесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно. Легко показать, что значение каждой из переменных D[v] в этом случае равно кратчайшему пути от s к v.

Таким образом для вычисления расстояния от s до t мы находим расстояние от s до всех вершин графа. Не известен ни один алгоритм, более эффективный, чем использующий этот принцип.

Следует иметь в виду, что на эффективность алгоритма очень сильное влияние оказывает очередность, в которой выбираются вершины u, v для проверки условия (1).

Рассмотрим общий алгоритм, определяющий расстояния от некоторой фиксированной вершины s (назо­вем ее источником) до всех остальных вершин графа. Обычно этот алгоритм называют алгоритмом Форда-Беллмана. При работе алгоритма предполагается, что граф не имеет контуров отрицательной длины.

1 BEGIN

2. FOR v eV DO D[v] := a[s, v]; D[s] := 0;

3. FOR k := 1 TO n-2 DO

4 FOR veV \ {s} DO

5 FOR u e V DO D[v] := min(D[v], D[u]+a[u, v])

6 END;

Очевидно, что сложность алгоритма есть 0(п³). В практике мы можем закончить вычисления, когда вы­полнение цикла 4 не вызывает изменения ни одной из переменных D[v], v е V. Это может произойти при k<n-2, однако такая модификация алгоритма не изменит существенным образом его сложности. Для редких графов (m«n²) удобнее представлять граф списками инцидентности ПРЕДШу] v eV. В этом случае заменим строку 5 на

FOR и е ПРЕДШу] DO D[v] := min(D[v], D[u]+a[u, v]).

Получим алгоритм, имеющий сложность 0(n*m).

На рис. 32 приведен пример, иллюстрирующий работу алгоритма Форда-Беллмана. Здесь циклы 4, 5 вы­полняются в порядке возрастания номеров вершин.

2	(3)	3
{$)/	\(3) A
s=i^(8)	\/(2)
(3)\	/(-5) \\

Too 1 00 00 3

oo oo 3 3 8

A = 00 00 00 1 —5

^L.2..

00 00 00 4 00

5

(4)

4

к	D[l]	1 D[2]	1 D[3]	1 D[4]	1 D[5]
	0	1	oo	oo	3
1	0	1	4	4	-1
2	0	1	4	3	-1
3	0	1	4	3	-1

Рис. 32 Работа алгоритма Форда-Беллмана