2. Алгоритмы поиска путей в графе.

Постановка задачи. Дан простой ориентированный граф с множеством вершин и множеством рёбер (без петель и кратных дуг). На множестве дуг задана неотрицательная вещественная функция (длины дуг). Длина пути из вершины в вершину определяется как сумма длин дуг, составляющих путь .

Задача 1. Одна из вершин выделена как источник. Требуется найти кратчайшие пути из источника ко всем остальным вершинам.

Задача 2. Найти кратчайшие пути между всеми парами вершин.

Для решения задачи 1 рассмотрим ″жадный″ алгоритм Дейкстры:

Алгоритм строит (использует) множество вершин, для которых кратчайшие пути из источника уже найдены. На каждом шаге к множеству добавляется та из оставшихся вершин которая ближе к источнику по сравнению с другими оствшимися вершинами. Так как длины дуг неотрицательны, то можно быть уверенны в том, что кратчайший путь проходит от источника к конкретной вершине через вершины множества . На каждом шаге алгоритма используется массив , в который записываются длины кратчайших путей для каждой вершины. Причём если , то значение становится окончательным.

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

Пусть dist – двумерный массив, причём dist [v,w] равно длине дуги (v,w) из вершины v в вершину w. Если такой дуги не существует, то полагаем dist [v,w]= ∞.

S ← {1}; вершина взята как источник

L[1] ← 0;

for v ← 2 to n do

L[v] ← dist [1,v]; pred[v] ← v

od;

for i ← 1 to n − 1 do

найдём вершину w ∈ V \ S, для которой значение L[w]минимально;

S ← S ∪ {w};

for ∀v ∈ V \ S do

m ← L[w] + dist [w,v];

if L[v] > m then {L[w]← m; pred[v] ← w

od

od.

Результат: L[v]− длина кратчайшего пути из вершины 1 в вершину v. При этом v, pred[v], pred[pred[v]],..., 1 есть вершины, составляющие кратчайший путь из вершины 1 в вершину v.

Обоснование алгоритма Дейкстры (кратко)

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

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

Рассмотренный алгоритм имеет временню сложность O (). Для рещения второй задачи существует алгоритм (Флойда , основанный на процедуре Уорщолла для вычисления транзитивного замыкания) со сложность O (), причем допускаются даже отрицательные веса дуг графа.

3. Алгоритмы нахождения минимального остова в графе

Постановка задачи. Дан простой неориентированный граф с множеством вершин и множеством рёбер (без петель и кратных дуг). На множестве рёбер задана вещественная функция (величина называется стоимостью ребра ). Остов графа −любой подграф , , графа , являющий деревом. Стоимость остова определяется как сумма стоимостей входящих в него рёбер.

Требуется найти остов графа , имеющий наименьшую стоимость по сравнению с другими возможными остовами.

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

″Жадный″ алгоритм Крускала, ориентированный на работу с рёбрами. Его времення сложность равна O(), где − число рёбер графа.

Алгоритм ближайшего соседа Прима и Дейкстры, ориентированный на работу с вершинми.Его временная сложность равна O(), где − число вершин графа.

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

1. (Предварительная сортировка рёбер.) Рёбра графа помещаются в очередь Q по неубыванию их стоимостей.

2. (Непосредственное построение остова.)

T ← ∅; искомое множество рёбер пока не построено

e ⟸ Q; извлекаем ребро из очереди

T ← T ∪ {e}; и помещаем его в искомое множество

while do множество должно содержать рёбер

e ⟸ Q; извлекаем очередное ребро из очереди

if ребро e не образует цикла с вершинами ранее включёнными в T

then T ← T ∪ {e}

od.

Обоснование (корректность) алгоритма

Пусть − рёбра построенного остова , записанные в порядке неубывания их стоимостей, – минимальный по стоимости остов графа графа , которыё содержит рёбра из для наибольшего возможного . Добавление в приводит к образованию цикла в остове , который будет содержать ребро , . Заметим, что , так как в противном случае ребро было бы включено в . Допущение также приводит к противоречию: стоимость остова , где , будет меньше стоимости минимального остова . Значит, . Однако, это противоречит способу выбора индекса . Следовательно, − минимальный остов.

Реализация алгоритма. Наиболее сложным в этом алгоритме является реализация оператора if Его эффективная реализация может быть осуществлена с помощью операций НАЙТИ и ОБЪЕДИНИТЬ для совокупности непересекающихся множеств.

Первоначально искомое дерево не имеет рёбер, т.е. ∅, и состоит из изолированных вершин множества . По мере включения в рёбер образуются частичные остовы (поддеревья), которые последовательно объединяются в единое дерево. Ребро включается в , если его концы принадлежат разным частичным остовам и . При этом остовы и объединяются в один остов . Каждый такой остов представлен множеством своих вершин, в качестве имени которого выбирается одна из его вершин.

(ПРИВОДИТСЯ РЕАЛИЗАЦИЯ − ПРОПУЩЕНО)

Временная сложность алгоритма Крускала. Времення сложность алгоритма равна

O(), поскольку за такое время может быть реализована как первая, так и вторая фазы алгоритма. Алгоритм Прима-Дейкстры может быть реализован со сложностью O ().