7.1.2. Алгоритм Краскала

Алгоритм Краскала (J.B. Kruskal) заключается в следующем.

Упорядочим все ребра исходного графа по неубыванию весов.

Просматривая последовательность слева направо, включаем в дерево каждое ребро, не образующее в дереве цикла. О том, что ребро (х_i х_j) образует цикл можно судить по тому, что из вершины х_i есть путь в вершину х_j по другим ребрам дерева. Процесс заканчивается, когда в дерево включено (m – 1) ребро.

Построим МСД для графа рис. 7.1 (а).

Упорядочим ребра: (х₄ х₆), (х₁ х₂), (х₂ х₅), (х₁ х₃), (х₁ х₆), (х₂ х₄), (х₃ х₆), (х₄ х₇), (х₆ х₇), (х₁ х₄), (х₅ х₇), (х₂х₇).

П росматривая список, включаем в дерево ребра (х₄ х₆), (х₁ х₂), (х₂ х₅), (х₁ х₃), (х₁ х₆) (рис. 7.5 (а)). Ребра (х₂ х₄) (рис. 7.5 (б)) и (х₃ х₆) (рис. 7.5 (в)) образуют цикл с уже построенными ребрами, поэтому в дерево не включаются. Следующее включаемое в дерево ребро (х₄ х₇) (рис. 7.5 (г)). Дерево построено.

3

4

х₅

5

1

 

б

а

   

Р исунок 7.5. Построение

МСД алгоритмом

Краскала

Суммарный вес ребер МСД равен 21.

Сложность алгоритма Краскала равна O(n log n), где n = U.

7.1.3. Кратчайшие пути

Пусть дан граф G(X, Γ), ребрам которого приписаны веса (стоимости), заданные матрицей C=c_ij_m×m. Задача о кратчайшем пути состоит в нахождении пути с минимальным суммарным весом от начальной вершины sX до конечной tX или от начальной вершины s X до всех остальных, при условии, что такие пути существуют.

Для нахождения кратчайших путей в графах разработано и реализовано на различных языках программирования много различных алгоритмов. К ним можно отнести алгоритмы: Дейкстры, Дейкстры-Грибова, Левита, Йена, Флойда-Уоршелла, Форда-Беллмана, Джонсона. Кратко рассмотрим эти алгоритмы. Алгоритм Дейкстры находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса. В процессе работы алгоритма поддерживаются три множества: М₀ – вершины, расстояние до которых уже вычислено (но, возможно, не окончательно); М₁ – вершины, расстояние до которых вычисляется; М₂ – вершины, расстояние до которых еще не вычислялось. В простейшем случае, сложность алгоритма составляет O(m² + n). Здесь m – количество вершин графа, n – количество ребер графа. Эффективность метода Дейкстры существенно зависит от того, как организован поиск во множестве М₁ вершины с наименьшим текущим расстоянием.

Модификация Грибова заключается в том, что вершины разбиваются на подмножества с близкими, отличающимися меньше чем на минимальную длину ребра, значениями кратчайшего пути в текущую вершину на данном шаге. Затем на каждой итерации берется непустое множество, соответствующее минимальному значению расстояния.

Алгоритм Левита позволяет найти кратчайшие пути от заданной вершины до всех остальных вершин. Алгоритм Левита напоминает метод Дейкстры – в процессе работы поддерживаются три множества (M₀, M₁, M₂). Вершины, входящие во множество М₁, делятся на два упорядоченных множества – основную и приоритетную очередь. Каждой вершине сопоставляется неотрицательное значение длины кратчайшего из известных на данный момент путей в нее из начальной вершины. В сравнении с методом Дейкстры метод Левита проигрывает на том, что некоторые вершины приходится обрабатывать повторно, а выигрывает на более простых алгоритмах включения и исключения вершин из множества М₁. Эксперименты показывают, что для графов с «геометрическим» происхождением, т.е. для графов, построенных на основе транспортных сетей и реальных расстояний, метод Левита оказывается наиболее быстрым. Он выигрывает и по размеру программы. Метод Левита обладает еще и тем преимуществом перед методом Дейкстры, что он применим в случае отрицательных длин ребер. Сложность алгоритма составляет O(n∙m).

Алгоритм Йена предназначен для нахождения нескольких путей минимальной суммарной длины во взвешенном графе с неотрицательными весами между двумя вершинами.

Алгоритм Беллмана-Форда решает задачу о нахождении кратчайших путей из одной вершины во все остальные для случая, когда веса ребер могут быть отрицательными. Кроме того алгоритм контролирует отсутствие циклов отрицательного веса, достижимых из исходной вершины. Если в графе нет циклов отрицательного веса, алгоритм находит кратчайшие пути из заданной вершины во все остальные, если же в графе есть циклы отрицательного веса, то, по крайней мере, для некоторых вершин кратчайшего пути не существует. Идея алгоритма, также как и алгоритма Дейкстры, основана на последовательной релаксации ребер, пока не будут найдены кратчайшие расстояния. Сложность алгоритма Форда - Беллмана есть O(n∙m).

Алгоритм Флойда-Уоршелла это динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Сложность алгоритма O(m³), т.е. алгоритм имеет кубическую сложность. Тем не менее, алгоритм определяет только кратчайшие расстояния между всеми парами вершин, но не сохраняет информации о кратчайших путях.

Алгоритм Джонсона позволяет найти кратчайшие пути между любыми двумя вершинами графа за O(m²log(m) + n∙m). Следовательно, для достаточно разреженных графов, он эффективнее альтернативных алгоритмов возведения в квадрат матрицы весов и алгоритма Флойда-Уоршелла. Этот алгоритм основан на идее изменения весов ребер графа. Если для ребер найти такую функцию, которая изменяет их веса, обеспечивая их неотрицательность и оставляя кратчайшие пути такими же (то есть состоящими из тех же ребер), то задачу поиска кратчайших путей между всеми парами вершин можно решить применив алгоритм Дейкстры для каждой вершины.

Рассмотрим подробно алгоритм Дейкстры (E.Dijkstra). Он основан на приписывании вершинам временных пометок, дающих верхнюю границу длины пути от s к этой вершине. Эти пометки постепенно уточняются, и на каждом шаге итерации точно одна из временных пометок становится постоянной. Это указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от s к рассматриваемой вершине.

Пусть l(x_i) пометка вершины x_i, а l(x_i)⁺ - постоянная пометка вершины.

1. Положить l(s)=0⁺ и считать эту пометку постоянной. Положить l(x_i)=∞ для всех x_i ≠ s и считать их временными. Положить p=s.

2. Для всех x_i Гр, пометки которых временные, изменить пометки в соответствии со следующим выражением

l(x_i) = min[l(x_i), l(p) + c(p,x_i)].

3. Среди всех вершин с временными пометками найти такую, для которой

l(x_i^*) = min[l(x_i)].

3. Считать пометку вершины x_i^* постоянной l(x_i^*)⁺ и положить p= x_i^*.

4. (Если надо найти лишь путь от s до t).

Если p=t, то l(p) – длина кратчайшего пути, конец. Если p ≠ t, перейти к п.2.

3. (Если надо найти путь от s до всех остальных вершин).

Если все вершины имеют постоянные пометки, то конец, если есть временные пометки, то перейти к п.2.

Сами пути можно получить при помощи рекурсивной процедуры с использованием соотношения:

l(x_i^’) + c(x_i^’, x_i)= l(x_i),

где x_i^’ – вершина непосредственно предшествующая вершине x_i в кратчайшем пути от s к x_i.

Пример. Дан взвешенный граф G(X,Г) и матрица весов C=׀׀c_ij׀׀_7×7 (рис. 7.6). Необходимо найти кратчайшие пути от начальной вершины x₁ ко всем остальным вершинам.

		х1	х2	х3	х4	х5	х6	х7
	х1	0	2				10	17
	х2	2	0	3				10
С=	х3		3	0	15		3
	х4			15	0	5		5
	х5				5	0	15
	х6	10		3		15	0	3
	х7	17	10		5		3	0

	x1	0+
	x2	∞
L=	x3	∞
	x4	∞
	x5	∞
	x6	∞
	x7	∞

Рисунок 7.6. Исходный граф и матрица весов

1. l(x₁)=0⁺; l(x_i)= ∞, для всех i ≠ 1, p = x₁.

Результаты итерации запишем в таблицу.

2. Гp ={x₂, x₆, x₇} – все пометки временные, уточним их:

l(x₂)=min[∞ ,0⁺+2]=2;

l(x₆)=min[∞, 0⁺+10]=10;

		1
	x1	0+
	x2	∞	2+
L=	x3	∞	∞
	x4	∞	∞
	x5	∞	∞
	x6	∞	10
	x7	∞	17

l(x₇)=min[∞, 0⁺+17]=17.

3. l(x_i*) = min[l(x_i)] = l(x₂) = 2.

4. x₂ получает постоянную пометку l(x₂) = 2⁺, p=x₂.

5. Не все вершины имеют постоянные пометки, поэтому

Гp ={x₁, x₃, x₇} – временные пометки имеют вершины x₃, x₇, уточняем их:

l(x₃)=min[∞, 2⁺+3]=5;

l(x₇)=min[17, 2⁺+10]=12.

6. l(x_i*) = min[l(x_i)] = l(x₃) = 5.

7. 	x1	0+
   	x2	∞	2+
   L=	x3	∞	∞	5+
   	x4	∞	∞	∞
   	x5	∞	∞	∞
   	x6	∞	10	10
   	x7	∞	17	12

   l(x₃) = 5⁺, p=x₃.

8. Не все вершины имеют постоянные пометки,

Гp ={x₂, x₄, x₆} – временные пометки имеют вершины x₄, x₆, уточняем их:

l(x₄)=min[∞ , 5⁺+15]=20;

l(x₆)=min[10, 5⁺+3]=8.

9. 		1	2	3	4
   	x1	0+
   	x2	∞	2+
   L=	x3	∞	∞	5+
   	x4	∞	∞	∞	20
   	x5	∞	∞	∞	∞
   	x6	∞	10	10	8+
   	x7	∞	17	12	12

   l(x_i*) = min[l(x_i)] = l(x₆) = 8.

10. l(x₆) = 8⁺, p=x₆.

11. Не все вершины имеют постоянные пометки

Гp ={x₁, x₅, x₇} – временные пометки имеют вершины x₅, x₇, уточняем их:

l(x₅)=min[∞ , 8⁺+15]=23;

l(x₇)=min[12, 8⁺+3]=11.

12. 	x1	0+
    	x2	∞	2+
    L=	x3	∞	∞	5+
    	x4	∞	∞	∞	20	20
    	x5	∞	∞	∞	∞	23
    	x6	∞	10	10	8+
    	x7	∞	17	12	12	11+

    l(x_i*) = min[l(x_i)] = l(x₇) = 11.

13. l(x₇) = 11⁺, p=x₇.

14. Не все пометки постоянные

	x1	0+
	x2	∞	2+
L=	x3	∞	∞	5+
	x4	∞	∞	∞	20	20	16+
	x5	∞	∞	∞	∞	23	23
	x6	∞	10	10	8+
	x7	∞	17	12	12	11+

Гp ={x₁, x₂, x₄, x₆} – временную пометку имеет вершина x₄, уточняем ее:

l(x₄)=min[20, 11⁺+5]=16.

15. l(x_i*) = min[l(x_i)] = l(x₄) = 16.

16. l(x₄) = 16⁺, p=x₄.

17. Не все пометки постоянные

		1	2	3	4	5	6	7
	x1	0+
	x2	∞	2+
L=	x3	∞	∞	5+
	x4	∞	∞	∞	20	20	16+
	x5	∞	∞	∞	∞	23	23	21+
	x6	∞	10	10	8+
	x7	∞	17	12	12	11+

Гp ={x₃, x₅, x₇} – временную пометку имеет вершина x₅, уточняем ее:

l(x₅)=min[23, 16⁺+5]=21.

18. l(x_i*) = l(x₅) = 21.

19. l(x₅) = 21⁺, p=x₅.

20. Все пометки постоянные.

Кратчайшие расстояния от вершины x₁ до всех вершин найдены. Как найти кратчайший путь до конкретной вершины, покажем на примере вершины x₅.

l(x₅) = 21, Гx₅ ={x₄, x₆},

21 = l(x₄)+ c(x₄, x₅)=16+5,

21 ≠ l(x₆)+ c(x₆, x₅)=8+15.

Это означает, что в вершину x₅ мы попали из вершины x₄.

Далее, l(x₄) = 16, Гx₄ ={x₃, x₅, x₇},

16 ≠ l(x₃)+ c(x₃, x₄)=5+15,

16 ≠ l(x₅)+ c(x₅, x₄)=21+15,

16 = l(x₇)+ c(x₇, x₄)=11+5.

Это означает, что в вершину x₄ мы попали из вершины x₇.

Далее, l(x₇) = 11, Гx₇ ={x₁, x₄, x₆},

11 ≠ l(x₁)+ c(x₁, x₇)=0+17,

11 ≠ l(x₄)+ c(x₄, x₇)=16+5,

11 = l(x₆)+ c(x₆, x₇)=8+3.

Это означает, что в вершину x₇ мы попали из вершины x₆.

Далее, l(x₆) = 8, Гx₆ ={x₁, x₃, x₅, x₇},

8 ≠ l(x₁)+ c(x₁, x₆)=0+10,

8 = l(x₃)+ c(x₃, x₆)=5+3,

8 ≠ l(x₅)+ c(x₅, x₆)=21+15,

8 ≠ l(x₇)+ c(x₇, x₆)=11+3.

Это означает, что в вершину x₆ мы попали из вершины x₃.

Далее, l(x₃) = 5, Гx₃ ={x₂, x₄, x₆},

5 = l(x₂)+ c(x₂, x₃)=2+3,

5 ≠ l(x₄)+ c(x₄, x₃)=16+15,

5 ≠ l(x₆)+ c(x₆, x₃)=8+3.

Это означает, что в вершину x₃ мы попали из вершины x₂.

Далее, l(x₂) = 2, Гx₂ ={x₁, x₃, x₇},

2 = l(x₁)+ c(x₁, x₂)=0+2,

2 ≠ l(x₃)+ c(x₃, x₂)=5+3,

2 ≠ l(x₇)+ c(x₇, x₂)=11+10.

Это означает, что в вершину x₂ мы попали из вершины x₁.

Кратчайший путь от вершины x₁ до вершины x₅ найден (рис.7.7):

Рисунок 7.7. Кратчайшие пути от вершины x₁ до всех вершин