Примеры решения задач

Пример 1. Пусть задан граф G = (X, U). Найти с помощью алгоритма Форда кратчайшие пути в заданном графе G от фиксированной вершины до всех остальных.

Решение: Рассмотрим матрицу смежности графа G:

	1	2	3	4	5	6	7	8	9
1	0	10	M	M	M	M	3	6	12	.
2	10	0	18	M	M	M	2	M	13
3	M	18	0	25	M	20	M	M	7
R=4	M	M	25	0	5	16	4	M	M
5	M	M	M	5	0	10	M	23	M
6	M	M	20	16	10	0	17	15	9
7	3	2	M	4	M	17	0	M	24
8	6	M	M	M	23	15	M	0	5
9	12	13	7	M	M	9	24	5	0

1.1. В качестве фиксированной вершины выбираем вершину x₁. Тогда ее вес V(1) = 0, а веса всех остальных вершин: V(2) = V(3) = … = V(9) =  = M.

1.2. Просматриваем первую строку матрицы смежности и выбираем поочередно все вершины, не помеченные литерой M. В результате мы сформировали следующий список вершин: x₂, x₇, x₈, x₉.

1.3. Для каждой из вершин, входящих в полученный список, проверяем истинность неравенства (1.8):

V(2) =   0 + 10 = 10; V(7) =   0 + 3 = 3; V(8) =   0 + 6 = 6;

V(9) =   0 + 12 = 12.

Значения весов для вершин x₃, x₄, x₅, x₆ не изменяются.

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

1.4. Производим пересчет весов для сформированного списка вершин:

для вершины x₂:

- V(2)  V(7) + r₂₇  10  3 + 2 ─ неравенство истинно, следовательно, вес вершины изменяется: V(2)¹ = 5,

- V(2)  V(9) + r₂₉  10  1 + 13 ─ неравенство ложно, следовательно, вес вершины не изменяется;

для вершины x₇:

- V(7)  V(2) + r₂₇  3  10 + 2 ─ неравенство ложно, следовательно, вес вершины не изменяется;

- V(7)  V(9) + r₇₉  3  12 + 24 ─ неравенство ложно, следовательно, вес вершины не изменяется.

для вершины x₈:

- V(8)  V(9) + r₈₉  6  12 + 5 ─ неравенство ложно, следовательно, вес вершины не изменяется;

для вершины x₉:

- V(9)  V(2) + r₂₉  12  10 + 13 ─ неравенство ложно, следовательно, вес вершины не изменяется,

- V(9)  V(7) + r₇₉  12  3 + 24 ─ неравенство ложно, следовательно, вес вершины не изменяется,

- V(9)  V(8) + r₈₉  12  6 + 5 ─ неравенство истинно, следовательно, вес вершины изменяется: V(9)¹ = 11.

1.5. Проверка условия: все ли вершины помечены.

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

2.1. Вычислим значение веса вершины x₃, его можно найти через x₂, x₄, x₆ или x₉. Однако значения весов вершин x₄ и x₆ нам пока не известны, поэтому производим расчет через вершины x₂ и x₉:

- V(3)  V(2) + r₂₃    5 + 18 - неравенство истинно, следовательно, вес вершины изменяется: V(3)¹ = 23,

- V(3)  V(9) + r₃₉  23  11 + 7 ─ неравенство истинно, следовательно, вес вершины изменяется: V(3)² = 18.

2.2. Вычислим значение веса вершины x₄, его можно найти через x₃, x₅, x₆ или x₇. Однако значения весов вершин x₅ и x₆ нам пока не известны, поэтому производим расчет через вершины x₃ и x₇:

- V(4)  V(3) + r₃₄    18 + 25 ─ неравенство истинно, следовательно, вес вершины изменяется: V(4)¹ = 43,

- V(4)  V(7) + r₄₇  43  3 + 4 ─ неравенство истинно, следовательно, вес вершины изменяется: V(4)² = 7.

2.3. Вычислим значение веса вершины x₅, его можно найти через x₄, x₆ или x₈. Однако значение веса вершины x₆ нам пока не известно, поэтому производим расчет через вершины x₄ и x₈:

- V(5)  V(4) + r₄₅    7 + 5 ─ неравенство истинно, следовательно, вес вершины изменяется: V(5)¹ = 12,

- V(5)  V(8) + r₅₈  12  6 + 23 ─ неравенство ложно, следовательно, вес вершины не изменяется.

2.4. Вычислим значение веса вершины x₆, его можно найти через x₃, x₄, x₅, x₇, x₈ или x₉:

- V(6)  V(3) + r₃₆    18 + 20 ─ неравенство истинно, следовательно, вес вершины изменяется: V(6)¹ = 38,

- V(6)  V(4) + r₄₆  38  7 + 16 ─ неравенство истинно, следовательно, вес вершины изменяется: V(6)² = 23,

- V(6)  V(5) + r₅₆  23  12 + 10 ─ неравенство истинно, следовательно, вес вершины изменяется: V(6)³ = 22,

- V(6)  V(7) + r₆₇  22  3 + 17 ─ неравенство истинно, следовательно, вес вершины изменяется: V(6)⁴ = 20,

- V(6)  V(8) + r₆₈  20  6 + 15 ─ неравенство ложно, следовательно, вес вершины не изменяется.

- V(6)  V(9) + r₆₉  20  11 + 9 ─ неравенство ложно, следовательно, вес вершины не изменяется,

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

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

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

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

Пример 2. Пусть задан граф G = (X, U). Найти с помощью алгоритма Дейкстра кратчайшие пути в заданном графе G от фиксированной вершины до всех остальных.

Решение: Рассмотрим матрицу смежности графа G:

	1	2	3	4	5	6	7	8	9
1	0	10	0	0	0	0	3	6	12	.
2	10	0	18	0	0	0	2	0	13
3	0	18	0	25	0	20	0	0	7
R=4	0	0	25	0	5	16	4	0	0
5	0	0	0	5	0	10	0	23	0
6	0	0	20	16	10	0	17	15	9
7	3	2	0	4	0	17	0	0	24
8	6	0	0	0	23	15	0	0	5
9	12	13	7	0	0	9	24	5	0

Постоянные пометки будем обозначать *, остальные временные.

1. l(x₁) = 0^*. l(x_i) = , x_i  x₁, p = x₁.

В качестве начальной вершины принимаем вершину x₁. Всем остальным вершинам графа присваиваем метки l(x_i) = .

Первая итерация

2. Г(p) = Г(x₁) = {x₂, x₇, x₈, x₉}. Возьмем вершину x₂ и из выражения (15.9) получим:

l(x₂)  min[l(x₂), l(x₁) + r(x₁, x₂)] = min[, 0^* + 10] = 10.

Аналогично вычисляем значения меток для других вершин, смежных с вершиной x₁: l(x₇) = 3, l(x₈) = 6, l(x₉) = 12.

3. В списке вершин графа выберем вершину, имеющую минимальное значение метки: Min[x₂, x₇, x₈, x₉, x₃, x₄, x₅, x₆] = min[10, 3, 6, 12, , , , ] = 3 ─ соответствует вершине x₇.

4. Вершина x₇ получает постоянную пометку l(x₇) = 3^*, p = x₇.

5. Не все вершины имеют постоянные пометки, переходим к п. 2.

Вторая итерация

2. Г(p) = Г(x₇) = {x₂, x₄, x₆, x₉} ─ все пометки временные. Из выражения (1.9) вычисляем:

l(x₂) = min[l(x₂), l(x₇) + r(x₇, x₂)] = min[10, 3^* + 2] = 5.

Аналогично l(x₄) = 7, l(x₆) = 17, l(x₉) = 12.

3. Min[x₂, x₄, x₆, x₈, x₉, x₃, x₅] = min[5, 7, 17, 6, 12, , ] = 5 ─ соответствует вершине x₂.

4. Вершина x₂ получает постоянную пометку l(x₂) = 5^*, p = x₂.

5. Перейдем к п. 2, т.к. не все вершины имеют постоянные пометки.

Третья итерация

2. Г(p) = Г(x₂) = {x₁, x₃, x₇, x₉}, только x₃ и x₉ имеют временные пометки. Из выражения (15.9) получим l(x₃) = min[, 5^* + 18] = 23, l(x₉) = min[12, 5^* + 13] = 12.

3. Min[x₃, x₄, x₈, x₆, x₉, x₅] = min[23, 7, 6, 17, 12, ] = 6 ─ соответствует вершине x₈.

4. Вершина x₈ получает постоянную пометку l(x₈) = 6^*, p = x₈.

5. Перейдем к п. 2, так как. не все вершины имеют постоянные пометки.

Четвертая итерация

2. Г(p) = Г(x₈) = {x₉, x₆, x₅}, x₅ и x₉ имеют временные пометки. Из выражения (15.9) получим:

l(x₅) = min[, 6^* + 23] = 29, l(x₉) = min[12, 6^* + r(x₈, x₉)] = 11.

3. Min[x₅, x₉, x₃, x₄, x₅] = min[29, 11, 23, 7, 29] = 7 ─ соответствует вершине x₄.

4. Вершина x₄ получает постоянную пометку l(x₄) = 7^*, p = x₄.

5. Переход к п. 2.

Пятая итерация

2. Г(p) = Г(x₄) = {x₃, x₆, x₅}. l(x₃) = 23, l(x₆) = 17, l(x₅) = 12.

3. Min[x₅, x₆, x₉, x₃] = min[12, 17, 11, 23] = 11.

4. Вершина x₉ получает постоянную пометку l(x₉) = 11^*, p = x₉.

5. Переход к п. 2.

Шестая итерация

2. Г(p) = Г(x₉) = {x₃, x₆} (берем только непомеченные вершины).

(x6) = min[l(x₆), l(x₉) + r(x₆, x₉)] = [17, 11^* + 9] = 17, l(x₃) = 18.

3. Min[x₅, x₆, x₃] = min[12, 17, 18] = 12.

4. Вершина x₅ получает постоянную пометку l(x₅) = 12^*, p = x₅.

5. Переход к п. 2.

Седьмая итерация

2. Г(p) = Г(x₅) = {x₆}.

l(x₆) = min[l(x₆), l(x₅) + r(x₅, x₆)] = [17, 12^* + 10] = 17.

3. Min[x₆, x₃] = min[17, 18] = 17.

4. Вершина x₆ получает постоянную пометку l(x₆) = 17^*, p = x₆.

5. Переход к п. 2.

Восьмая итерация.

2. Г(p) = Г(x₃) = .

l(x₃) = min[18] = 18, p = x₃. Все вершины помечены.

Итак, получили кратчайшие пути от вершины x₁ до всех остальных:

x₁  x₂(5^*), x₁  x₃(18^*), x₁  x₄(7^*), x₁  x₅(12^*), x₁  x₆(17^*), x₁  x₇(3^*), x₁  x₈(6^*), x₁  x₉(11^*);

x₁  x₇  x₂  x₃(18^*), x₁  x₇  x₂(5^*), x₁  x₈(6^*), x₁  x₈  x₉(11^*), x₁  x₇  x₆(17^*), x₁  x₇  x₄  x₅(12^*), x₁  x₇  x₄(7^*).

Длину цепи, т.е. суммарную стоимость весов пройденных ребер, можно получить при помощи описанной ранее рекурсивной процедуры.

Например: x₁  x₃(18^*), сумму 18 дает вершина x₉ с ребром {x₉ ─ x₃}:

имеем x₃  x₉(11^*), сумму 11 дает вершина x₈ с ребром {x₈ ─ x₉}.

имеем x₃  x₉  x₈(6^*), сумму 6 дает вершина x₁ с ребром {x₁ ─ x₈}.

Тогда имеем кратчайший путь x₃  x₉  x₈  x₁ длиной 18.

Результат построения кратчайших путей в графе G показан на рис. 15.33.

Рис. 15.33. Граф G