Алгоритм Форда

Приведем алгоритм Форда нахождения маршрутов с минимальной суммарной стоимостью ребер. Будет анализироваться помеченный граф с весами на ребрах. Граф с весами на ребрах называется взвешенным.

1°. Строим матрицу R взвешенного графа G.

Если вершины не смежны между собой, то в матрице ставим M. Фиксируем одну вершину x_k и приписываем ей вес V(k) = 0, всем остальным вершинам приписываем вес V(j) = M.

2°. Берем произвольную вершину x_j ¹ x_k и находим смежную с x_j вершину x_i, имеющую вес r_i,j. В начальный момент в качестве вершины x_i берем фиксированную x_k. Для x_j и x_i проверяется выполнение неравенства

V(j) > V(i) + r_i,j. (15.8)

Если оно выполняется, то прежний вес V(j) вершины x_j заменяется суммой V(i) + r_i,j. В противном случае, вес V(j) остается неизменным.

3°. Повторяем пп. 1, 2 пока не рассмотрены все вершины.

4°. Конец работы алгоритма.

Для уменьшения объема вычислений операцию пересчета индексов сначала выполняют для всех x_j, смежных с фиксированной x_k, а затем продолжают это для вершин, смежных с выбранными ранее.

Операция пересчета производится для всех вершин графа до тех пор, пока ни одна из вершин не сможет принимать нового значения V(j). Тогда длинами кратчайших цепей от x_j до x_k будут величины V(j), полученные в результате замен переменных весов V(j) на новые.

Например, для графа G рис. 15.31 выполним алгоритм Форда.

Рис. 15.31. Пример графа G

В матрице R по главной диагонали проставлены нули, так как в графе G нет петель. При отсутствии связи между вершинами проставлен знак М.

Матрица смежности этого графа запишется так:

					M		M	.
			M	M	M
		M				M
R = 4		M				M	M
	M	M				M
			M	M	M
	M			M

Принимаем вес вершины х ₁ равным V(1) = 0, V(2) = V(3) = … = V(7) = M = ¥.

1) Фиксированная вершина x_k = x ₁.

2) Просматриваем все пары x_i, x_j и проверяем выполнение неравенства (15.8).

Пусть i = 1, j = 2, тогда имеем V(1) = 0, V(2) = M, r_1,2 = 4.

Условие неравенства V(2) = M > V(1) + r _1,2 = 0 + 4 = 4. Поэтому вершине x ₂ присваиваем новый вес V(2)¹ = 4.

Для вершин, у которых r_i,j = M, неравенство (15.8) выполняться не будет и вес V(j) останется прежним.

Далее, для x ₃: V(3) = M > V(1) + r _1,3 = 0 + 5 = 5 и V(3)¹ = 5.

Для x ₄: V(4) = M > V(1) + r _1,4 = 0 + 9 = 9 и V(4)¹ = 9.

Для x ₆: V(6) = M > V(1) + r _1,6 = 0 + 2 = 2 и V(6)¹ = 2.

Теперь произведем пересчет индексов для вершин, смежных с x ₁, с учетом пути через другие смежные вершины.

Для x ₂: V(2) = 4 < V(6) + r _2,6 = 2 + 5 = 7, значит, индекс вершины остается без изменения.

Для x ₄: V(4) = 9 > V(3) + r _4,3 = 5 + 3 = 8, следовательно, меняем значение V(4) с 9 на 8 (см рис. 1.31).

Для x ₆: V(6) = 2 < V(2) + r _2,6 = 4 + 5 = 9, здесь индекс остается без изменения.

Произведем пересчет индексов для вершин, несмежных с фиксированной вершиной x ₁.

Вычислим индекс вершины x ₅, его можно найти через x ₃, x ₄ или x ₇. Индекс x ₇ равен М, поэтому для нее неравенство (15.8) не выполняется.

Вычислим индекс вершины x ₅ через x ₄. Получим V(5)₄¹ = M > V(4)¹ + r _4,5 = 8 + 8 = 16.

Приняв V(5)¹ = 16 за старое значение индекса, пересчитаем его через x ₃:

V(5)₃¹= 16 > V(3)¹ + r_3,5 = 5 + 3 = 8.

Так как условие (15.8) выполняется, то значение индекса V(5)¹ = 16 заменяем на V(5)² = 8.

Индекс x ₇ можно определить через x ₂, x ₃, x ₅, x ₆.

V(7)₂¹ = M > V(2)¹ + r_2,7 = 4 + 6 = 10,

V(7)₅¹ = M > V(5)¹ + r_5,7 = 8 + 1 = 9,

V(7)₃¹ = M > V(3)¹ + r_3,7 = 5 + 7 = 12,

V(7)₆¹ = M > V(6)¹ + r_6,7 = 2 + 3 = 5.

Итак, V(1) = 0, V(2) = 4, V(3) = 5, V(4) = 8, V(5) = 8, V(6) = 2, V(7) = 5.

Алгоритм Форда дает кратчайшее расстояние от выбранных вершин до фиксированной вершины, а сами цепи не определяет.

Для определения цепи от выбранной вершины до фиксированной воспользуемся равенством V(j) ─ V(i) = r_i,j.

Например, найдем путь от x ₇ до x ₁. Ищется предпоследний шаг при пересчете индекса V(7)¹. Это x ₇ ─ x ₆. Затем для x ₆ определяется вершина пересчета. Это x ₆ - x1. Следовательно, кратчайший путь x ₇ ─ x ₆ ─ x ₁, а кратчайшее расстояние между вершинами x ₁ и x ₇ определено ранее V(7)¹ = 5.

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

На рис. 15.32 приведен пример, когда необходимо определить путь из вершины

Рис. 15.32. Пример нахождения минимального маршрута

А в В с минимальной стоимостью. При выборе ближайшей вершины 1 из вершины А получим длину маршрута АВ = 13. Например, длины маршрутов А – 1 – 6 – 7 – В или А – 1 – 2 – 7 – 8 – В равны 13. В то же время все другие маршруты (через вершину 3) дают длину маршрута АВ = 8 (например, А – 3 – 4 – 5 – В).

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

Дата добавления: 2015-10-26