l(e)

8.3. Кратчайшие пути в графе

Задан связный граф G = (V, E) с ребрами, взвешенными действительными положительными числами. В данном случае вес ребра e = vivj будем считать его длиной l(e) = l(vivj). Требуется найти цепь с минимальной длины, соединяющую две заданные вершины в графе G, т. е. такую цепь, для которой величина ∑

e c

минимальна.

Для решения этой задачи можно применить алгоритм Форда, который заключается в следующем.

Пусть в графе G надо найти путь от вершины v1 к вершине vn. Каждой

вершине vi V припишем индекс λ(vi). При этом положим λ(v1) = 0 и λ(vi) = + ∞ для i ≠ 1.

На каждом шаге алгоритма отыскивается ребро vivj, для которого λ(vi) –

λ(vj) > l(vivj), и индекс λ(vi) заменяется на λ′(vi) = λ(vj) + l(vivj). Повторение таких шагов продолжается, пока находятся ребра, для которых выполняется

данное неравенство.

В результате выполнения данной процедуры определяется длина кратчайшего пути, равная λ(vп). Сам путь надо строить, начиная с вершины vп и двигаясь обратно к вершине v1. При этом всякий раз надо выбирать такую вершину vj после вершины vi, чтобы выполнялось равенство λ(vi) – λ(vj) = l(vivj).

Пусть в графе на рис. 8.3 требуется найти кратчайший путь из вершины v1 к вершине v8. Возле каждого ребра дана его длина. Покажем изменение

индексов вершин:
v1	v2	v3	v4	v5	v6	v7	v8
______________________________
0	∞	∞	∞	∞	∞	∞	∞
	1	10	6	11	14	9	16
					13		15

	v2		10	v5
	1	10	1	2	5
v1
	10		4	2	v8
	v3	4	1	v6	8
	6			5

v4v7

3

Рис. 8.3. Граф со взвешенными ребрами и выделенным кратчайшим путем

52

Длина кратчайшей цепи в данном графе равна 15. Двигаясь от вершины v8

к вершине v1, подходим сначала к вершине v6, так как λ(v8) – λ(v6) = l(v6v8) = 2. Следуя тому же правилу, проходим вершину v5 и затем вершину v2. На рис. 8.3

выделены ребра, принадлежащие найденному пути.

53