Волновой алгоритм построения кратчайшего пути для невзвешенного графа

0. Вершина Xн помечается 0, остальные вершины считаются непомеченными.

1. i=i+1. Помечаются индексом i все непомеченные ранее вершины, в которых есть дуги от помеченных вершин. Если помечена вершина Хк, то выполняется п.2. Иначе, если в текущем значении индекса i оказались помеченными какие-либо вершины, то выполняется п.1. Иначе делается вывод, что пути из вершины Хн в Хк нет.

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

3. При движении от вершины Хн по выделенным дугам оказывается построены все кратчайшие пути к вершине Хк.

Волновой алгоритм построения кратчайшего пути для взвешенного графа

1. Вершина Х_н получает вес V = 0, ее номер вводится в массив М номеров
вершин, изменивших вес. Остальные вершины X_i получают вес V_i = ∞, их номера не
попадают в массив М.

2. Если массив M пуст, то выполняется п. 3, иначе выбирается с исключением
из него очередная вершина X_i, и пересчитываются веса вершин, принадлежащих исходу G(X_i) вершины X_i: " X_i Î G (X_i)(V_j = min (V_j V_i + l_ij)). Если вес V_j уменьшается, то номер j включается в М. Снова выполняется п. 2.

3. Если вес V_i = ∞, то делается вывод, что пути из вершины Х_н к вершине X_k
нет, иначе выполняется процедура выделения дуг, такая же, как в волновом алгоритме
для невзвешенного графа, за исключением того, что разность весов вершин X_i и X_j должна быть равна l_ij.

4. После выделения дуг строятся кратчайшие пути, длины которых равны V_k.
Пример

 

 

1. V_i = V₁ = 0, V₂ = V₃ = V₄ = V₃ = V₆ = ∞, M = {1}

2. M ≠ 0, i = 1, M = 0, G(X₁) = {X₂, X₃}; V₂ = min (∞, 0 + 1)=1; M ={2}

V_i = min (∞, 0 + 4) = 4; M ={2, 3};

2. M ≠ 0, i = 2, M = {3}, G(X₂) = {X₃, X₄}; V₃ = min (4, 1 + 2)=3; M = {3}; V₄ = min (∞, 1 + 5) = 6; M={3, 4};

2. M ≠ 0, i = 3, M = {4}, G(X₃) = {X₄, X₅}; V₄ = min (6, 3 + 2)=5; M = {4}; V₅ = min (∞, 3 + 4) = 7; M={4, 5};

2. M ≠ 0, i = 4, M = {5}, G(X₄) = {X₅, X₆}; V₅ = min (7, 5 + 1)=6; M = {5}; V₆ = min (∞, 5 + 4) = 9; M={5, 6};

2. M ≠ 0, i = 5, M = {6}, G(X₆) = {X₆}; V₆ = min (9, 6 + 2)=8; M = {6};

2. M ≠ 0, i = 6, M = {0}, G(6) = {0};

3. G^-1(X₆) = {X₄, X₅}; V_x6 - V_x5 = 2; l₆ = 2, * V_x6 - V_x4 = 3, l_{4, 6} = 4.

G^-1(X₅) = {X₃, X₄}; V_x5 - V_x4 = 1; l_{4, 5} = 1, * V_x5 - V_x3 = 3, l_{5, 3} = 4.

G^-1(X₄) = {X₂, X₃}; V_x4 - V_x3 = 2; l_{3, 4} = 2, * V_x4 - V_x2 = 4, l_{2, 4} = 5.

G^-1(X₃) = {X₁, X₂}; V_x3 - V_x2 = 2; l_{2, 3} = 2, * V_x3 - V_x1 = 3, l_{1, 3} = 4.

G^-1(X₂) = {X₁}; V_x2 - V_x1 = 1; l₁ = 1, *

Построен кратчайший путь (Xн, Xк) длиной 8:

(X_н = Х₁, Х₂)( Х₂, Х₃)( Х₃, Х₄)( Х₄, Х₅)( Х₅, Х₆ = Х_к).

Процесс решения можно оформить в виде таблицы:

Х1	Х2	Х3	Х4	Х5	Х6	М
0	∞	∞	∞	∞	∞	1
0	1	4	∞	∞	∞	2, 3
0	1	3	6	∞	∞	3, 4
0	1	3	5	7	∞	4, 5
0	1	3	5	6	9	5, 6
0	1	3	5	6	8	6
0	1	3	5	6	8	0

Волновой алгоритм построения длиннейшего пути во взвешенном графе

 

Используется волновой алгоритм построения кратчайшего пути для взвешенного графа со следующим отличием:

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

2. Во втором пункте алгоритма V_j = max (V_j, V_i + l_ij)

Х1	Х2	Х3	Х4	Х5	Х6	М
0	0	0	0	0	0	1
0	1	4	0	0	0	2, 3
0	1	4	6	0	0	3, 4
0	1	4	6	8	0	4, 5
0	1	4	6	8	10	5, 6
0	1	4	6	8	10	6
0	1	4	6	8	10	0

 

Обратный ход:

 

 

Построены три длиннейшие пути:

1. (Х₁, Х₂)( Х₂, Х₄)( Х₄, Х₆)

2. (Х₁, Х₃)( Х₃, Х₄)( Х₄, Х₆)

3. (Х₁, Х₃)( Х₃, Х₅)( Х₅, Х₆)

Алгоритм нахождения компонент связанности

Вершины Х_i и X_j слабо связны, если существует путь (Х_i и X_j) в графе (G, X).

Вершины X_i и X_j сильно связаны, если существуют пути (Х_i и X_j)и (X_j и Х_i) в графе (G, X).

Если в графе нет путей Х_i и X_jи нет обратного пути из Х_j в X_i, то вершины Х_i и X_j не связаны.

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

Пример 3.2.1

 

 

Компоненты связности: 1) {x1, x2, x3, x4}; 2) {x5, x6, x7}; 3) {x8}.

Между компонентами - только слабая связность: есть пути из вершин компоненты 1) в вершины компоненты 2) и 3) и из вершин компоненты 2) в 3).

Алгоритм построения компонент связности в неориентированном графе

1. i=0. Все вершины графа не отмечены.

2. i=i+1. Выбираем очередную неотмеченною вершину, отмечаем ее и все
связанные с нею вершины значением индекса i с помощью распространения волны
отметок по ребрам, идущим от уже отмеченных индексом i вершин. Таким образом,
выделяется i компонента связности. Если есть еще неотмеченные вершины, то
выполняется п. 2, иначе выделение компонент связности закончено.

Пример 3.2.2

1.i = 0

2. i = 1. Отмечаем индексом i =1 вершину Х₁, и связанные с ней вершины

Х₃, Х₇, Х₉. Получена первая компонента связности: 1{ Х_1, Х₃, Х₇, Х₉}.

3. i =2. Отметим индексом i = 2 вершину Х₄ и вершины Х₆, Х₁₀. Построена

вторая компонента связности: 2{ Х₂, Х₆, Х₁₀)

4. i=3 Отмечаются индексом i = 3 вершины X₄ и Х₈. Построена третья

компонента связности: 3{X₄, X₈}.

5. i=4. Отметим индексом i = 4 вершину Х₅, которая формирует четвертую компоненту связности -{X₅}.

Дерево. Остов.

Деревом называется конечный связный граф без циклов. Из свойств связности и отсутствия циклов следует, что у дерева количество компонент связности р =1 и цикломатическое число g = 0 = m – n + 1, отсюда следует что m = n -1; т.е. число ребер в дереве на единицу меньше числа вершин. Ниже приведены примеры деревьев.

Рис.3

Остов – это подграф (частичный), который может быть построен из графа удалением некоторых ребер и который является деревом.

В общем случае для графа можно построить несколько остовов. Для приведенного ниже графа построен один из возможных вариантов остова.

 

Для несвязного графа рассматриваются отдельные его компоненты. Остов такого графа – совокупность его компонент.

⇐ Предыдущая123Следующая ⇒

Поделиться:

Популярное:

1. Cодержательные и организационные особенности построения курса «Основы технологии интеллектуальной адаптации коренных народов северных регионов»
2. Dermal mask, Коллагеновая тканевая маска для лица, 23гр -
3. I. Его руки подняты для благословения.
4. I. Путивль.-Торжественная встреча патриарха.-Подношения.-Греческие монахи.
5. I. Смотрите на Него, приготовляющего для Себя престол.
6. I. ТИТУЛ «ИНТЕРНАЦИОНАЛЬНЫЙ ЧЕМПИОН ПО КРАСОТЕ» (C.I.B.) ДЛЯ ПОРОД С ОБЯЗАТЕЛЬНЫМИ И НЕОБЯЗАТЕЛЬНЫМИ РАБОЧИМИ ИСПЫТАНИЯМИ СОГЛАСНО НОМЕНКЛАТУРЕ FCI.
7. II. Извлеки урок для совести.
8. II. Путивль. – Иностранцы в России. – Отношение к ним русских. – Сербский митрополит. – Посещение патриарха воеводой. – Описание города Путивля, крепости и церкви.
9. II. ТЕКСТЫ ДЛЯ РАБОТЫ НАД ГОЛОСОМ.
10. III. БАЗИСНЫЕ РАЗДЕЛЫ ДЛЯ ПОВТОРЕНИЯ
11. III. Реакции, характерные только для альдегидов
12. IV. Выезд из Путивля. – Состояние дорог. – Севск. – Воевода. – Угощение им патриарха. – Дальнейший путь. – Земледельческие орудия. – Посевы.