Задания для самостоятельной работы

1. Задайте произвольный граф G = (X, U), |X| = 5, |U| = 7. Определите количество маршрутов длиной 2, 3, 4.

2. Составьте словесный алгоритм определения маршрутов в графе.

3. Составьте структурную схему алгоритма определения маршрутов в графе.

4. Задайте произвольный граф G = (X, U), где ½X½ = 6; ½U½ = 10. Постройте маршрут, цепь, цикл, простую цепь, простой цикл. Покажите на примере отличия между этими видами маршрутов.

5. Составьте структурную схему алгоритма или словесный алгоритм определения связности произвольного неориентированного графа.

6. Задайте произвольный граф G = (X, U), где ½X½ = 6; ½U½ = 18. Приведите пример правильного разреза и разреза графа.

7. Приведите пример графа, имеющего точку сочленения.

8. Приведите пример неразделимого графа.

9. Приведите пример графа блоков.

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

 

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

 

Нахождение кратчайших маршрутов (цепей)

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

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

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 нет петель. При отсутствии связи между вершинами проставлен знак М.

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

	1	2	3	4	5	6	7
1	0	4	5	9	M	2	M	.
2	4	0	M	M	M	5	6
3	5	M	0	3	3	M	7
R = 4	9	M	3	0	8	M	M
5	M	M	3	8	0	M	1
6	2	5	M	M	M	0	3
7	M	6	7	M	1	3	0

Принимаем вес вершины х ₁ равным 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 – В).

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

Алгоритм Дейкстры

Рассмотрим алгоритм Дейкстры нахождения кратчайшей цепи между двумя заданными вершинами х _s и х _t.

Метод основан на приписывании вершинам временных пометок, причем пометка вершины x_i дает верхнюю границу длины пути от вершины х _s к этой вершине. Значения этих пометок постепенно уменьшаются на основе итерационной процедуры и на каждом шаге итерации точно одна из временных пометок становится постоянной. Это говорит о том, что пометка дает длину кратчайшей цепи от вершины х _s к рассматриваемой вершине.

Алгоритм:

Пусть l (x_i) ─ пометка x_i.

(блок присвоения начальных значений)

1°. Пусть l (s) = 0. Положим l (x_i) = ¥ для всех x_i ¹ s и считаем их пометки временными; пусть p = s.

(блок обновления пометок)

2°. Для всех x_i Î Г(p), пометки которых временные, изменить пометки в соответствии с выражением

                                 l (x_i) min[ l (x_i); l (p) + r(p, x_i)]                  (15.9)

(блок превращения пометки в постоянную)

3°. Среди всех вершин с временными пометками найти такую, что l (x_i ^*) =     

= min[ l (x_i)].

4°. Считать пометку x_i ^* постоянной и положить p = x_i ^*.

5°.

а) Если надо построить цепь от вершины х _s к вершине х _t:

Если p = t, то l (p) ─ длина кратчайшей цепи, останов.

Если p ¹ t, переход к п. 2°.

б) Если надо построить цепь от вершины х _s ко всем остальным вершинам:

Если все вершины отмечены как постоянные, то эти пометки дают длины кратчайших цепей, останов.

Если некоторые вершины являются временными, переход к п. 2°.

Рассмотрим последовательность выполнения алгоритма Дейкстра на примере построения кратчайших цепей в графе (см. рис. 15.31).

Матрица смежности графа G имеет следующий вид:

	1	2	3	4	5	6	7
1	0	4	5	9	0	2	0	.
2	4	0	0	0	0	5	6
3	5	0	0	3	3	0	7
R = 4	9	0	3	0	8	0	0
5	0	0	3	8	0	0	1
6	2	5	0	0	0	0	3
7	0	6	7	0	1	3	0

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

Вначале нам необходимо выбрать начальную вершину x_s, которую мы будем использовать в дальнейшем, в качестве фиксированной. Примем в качестве такой вершины x ₁. Метки всех остальных вершин, отличных от вершины x _1, считаем равными ¥, а значение p = x ₁.

1°. L(x ₁) = 0^*. L(x_i) = ¥, " x_i ¹ x ₁, p = x ₁.

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

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

2°. Для всех вершин, смежных с начальной вершиной x ₁ и имеющих временные метки G(x ₁) = { x ₂, x ₃, x ₄, x ₆}, пересчитываем в соответствии с выражением (15.9) действующие значения их меток.

Для l (x ₂) min[ ¥; 0^*+ 4 ] = 4.

Для l (x ₃) min[ ¥; 0^*+ 5 ] = 5.

Для l (x ₄) min[ ¥; 0^*+ 9 ] = 9.

Для l (x ₆) min[ ¥; 0^*+ 2 ] = 2.

3°. Выбираем из списка вершин с временными метками вершину с временной меткой, имеющей минимальное значение:

Min [ 4, 5, 9, ¥, 2, ¥ ]

         x ₂ x ₃ x ₄ x ₅ x ₆ x ₇

Очевидно, что такой вершиной является вершина x ₆.

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

5°. Поскольку не все вершины имеют постоянные пометки, переходим к п. 2°.

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

2°. Для всех вершин, смежных с текущей вершиной x ₆ и имеющих временные метки G(x ₆) = { x ₂, x ₇}, пересчитываем в соответствии с выражением (15.9) действующие значения их меток:

Для l (x ₂) min[ 4; 2^*+ 5 ] = 4.

Для l (x ₇) min[ ¥; 2^*+ 3 ] = 5.

Новое значение метки для вершины x ₂ оказалось больше текущего, поэтому оставляем текущее значение временной метки, а для вершины x ₇ заменяем значение l (x ₇) = ¥ на полученное значение l (x ₇) = 5.

3°. Выбираем из списка вершин с временными метками вершину с временной меткой, имеющей минимальное значение:

Min[ 4, 5, 9, ¥, 5]

    x ₂ x ₃ x ₄ x ₅ x ₇

Очевидно, что такой вершиной является вершина x ₂.

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

5°. Поскольку не все вершины имеют постоянные пометки, переходим к п. 2°.

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

2°. Для всех вершин, смежных с текущей вершиной x ₂ и имеющих временные метки G(x ₂) = { x ₇}, пересчитываем в соответствии с выражением (15.9) действующие значения их меток.

Для l (x ₇) min[ 5; 4^*+ 6 ] = 5.

Новое значение метки для вершины x ₇ оказалось больше текущего, поэтому оставляем текущее значение временной метки l (x ₇) = 5.

3°. Выбираем из списка вершин с временными метками вершину с временной меткой, имеющей минимальное значение:

 Min [ 5, 9, ¥, 5 ]

     x ₃ x ₄ x ₅ x ₇

В данном случае две вершины имеют одинаковые метки l (x ₃) = l (x ₇) = 5 и мы можем выбрать любую из них. Пусть это будет вершина x ₃.

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

5°. Поскольку не все вершины имеют постоянные пометки, переходим к п. 2°.

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

2°. Для всех вершин, смежных с текущей вершиной x ₃ и имеющих временные метки G(x ₃) = { x ₄, x ₅, x ₇} пересчитываем в соответствии с выражением (1.9) действующие значения их меток:

для l (x ₄) min[ 9; 5^*+ 3 ] = 8,

для l (x ₅) min[ ¥; 5^*+ 3 ] = 8,

для l (x ₇) min[ 5; 5^*+ 7 ] = 5.

Новое значение метки для вершины x ₇ оказалось больше текущего, поэтому оставляем текущее значение временной метки, а для вершин x ₄ и x ₅ заменяем текущие значения меток на новые.

3°. Выбираем из списка вершин с временными метками, вершину с временной меткой, имеющей минимальное значение:

Min [ 8, 8, 5 ]

     x ₄ x ₅ x ₇

Очевидно, что такой вершиной является вершина x ₇.

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

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

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

2°. Для всех вершин, смежных с текущей вершиной x ₇ и имеющих временные метки G(x ₇) = { x ₅}, пересчитываем в соответствии с выражением (15.9) действующие значения их меток.

Для l (x ₅) min[ 8; 5^*+ 1 ] = 6.

3°. Выбираем из списка вершин с временными метками вершину с временной меткой, имеющей минимальное значение:

Min [ 8, 6 ]

     x ₄ x ₅

Такой вершиной является вершина x ₅.

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

5°. Поскольку не все вершины имеют постоянные пометки, переходим к п. 2°.

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

2°. Из вершин, смежных с текущей вершиной x ₃ и имеющих временные метки осталась только вершина x ₄: G(x ₁) = { x ₄}. Пересчитываем значение ее метки в соответствии с выражением (15.9):

для l (x ₄) min[ 8; 6^*+ 8 ] = 8.

Новое значение метки для вершины x ₄ оказалось больше текущего, поэтому оставляем текущее значение временной метки.

3°. В списке вершин с временными метками только один элемент:

Min [ 8, ]

     x ₄

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

5°. Поскольку все вершины графа имеют постоянные метки, конец алгоритма.

Таким образом, мы построили кратчайшие пути от вершины x ₁ до вершин x ₂, x ₃, x ₆ напрямую:

x ₁ ® x ₂(4^*), x ₁ ® x ₃(5^*), x ₁ ® x ₆(2^*),

а до вершин x ₄, x ₅, x ₇ через промежуточные:

x ₁ ® x ₃ ® x ₄(8^*);

x ₁ ® x ₆ ® x ₇ ® x ₅(6^*);

x ₁ ® x ₆ ® x ₇(5^*).

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

l (x_s) + r (x_s, x_j) = l (x_i),

т.е. проверяется, какая из вершин, смежных вершине x_s, дает вместе с весом ребра r (x_s, x_j) сумму, равную l (x_i).

Например: l (x ₄)= 8. Поскольку вершина x ₄ напрямую не связана с вершиной x ₁, то определим кратчайший путь из x ₁ в x ₄:

l (x ₁) = l (x ₄)─ r (x ₃, x ₄) = 8 – 3 = 5 = l (x ₃) - r (x ₁, x ₃) = 5 – 5 = 0.

Таким образом, построена кратчайшая цепь между вершинами x ₁ и x ₄: x ₁ ® x ₃ ® x ₄.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Пример 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

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. Какой граф называется взвешенным?

2. Как определяется кратчайшая цепь в графе?

3. Что представляет собой алгоритм Форда?

4. Для чего используется алгоритм Форда?

5. Какова сложность алгоритма Форда?

6. На чем основан метод Дейкстры?

7. Для чего используется алгоритм Дейкстры?

8. Какова сложность алгоритма Дейкстры?

9. Как определяется последовательность прохождения вершин в кратчайшей цепи?

10. В каком случае алгоритмы Форда и Дейкстры не позволяют найти кратчайший по стоимости путь?