Взвешенные графы. Остовные деревья. Кратчайшие пути

Взвешенный граф
Если каждому ребру в графе / дуге в орграфе сопоставлено некоторое число, называемое весом ребра / дуги, то граф / орграф называется взвешенным.

Подграф
Граф, все вершины и ребра которого принадлежат исходному графу.

Остовной подграф
Остовным называется подграф, которое содержит все вершины исходного графа.

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

Теорема Кирхгофа

Алгоритм Краскала, 1956
Сортируем ребра графа по возрастанию весов.
Полагаем, что каждая вершина относится к своей компоненте связности.
Проходим ребра в "отсортированном" порядке. Для каждого ребра выполняем:
если вершины, соединяемые данным ребром, лежат в разных компонентах связности, то объединяем эти компоненты в одну, а рассматриваемое ребро добавляем к минимальному остовному дереву;
если вершины, соединяемые данным ребром лежат в одной компоненте связности, то исключаем ребро из рассмотрения.
Если есть еще нерассмотренные ребра и не все компоненты связности объединены в одну, то переходим к шагу 3, иначе выход.

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

Алгоритм Прима
На каждом шаге вычеркиваем из графа дугу максимальной стоимости с тем условием, что она не разрывает граф на две или более компоненты связности, т.е. после удаления дуги граф должен оставаться связным.
Для того, чтобы определить, остался ли граф связным, достаточно запустить поиск в глубину от одной из вершин, связанных с удаленной дугой.
Условие окончания алгоритма?
Например, пока количество ребер больше либо равно количеству вершин, нужно продолжать, иначе – остановиться.

Задача
Телевизионная компания планирует подключение к своей кабельной сети пяти новых районов. На рисунке показана структура планируемой сети и расстояния (в км) между районами и телецентром. Необходимо спланировать наиболее экономичную кабельную сеть.

Ребра AD и CE имеют минимальный вес, равный 5.
Произвольно выбирается ребро AD (выделено на рисунке). Теперь наименьший вес, равный 5, имеет ребро CE.
Так как добавление CE не образует цикла, то
выбираем его в качестве второго ребра.
Аналогично выбираем ребро DF, вес которого
равен 6.

Следующие ребра — AB и BE с весом 7. Произвольно выбирается ребро AB, выделенное на рисунке. Ребро BD выделено красным, так как уже существует путь (зелёный) между A и D, поэтому, если бы это ребро было выбрано, то образовался бы цикл ABD.
Аналогичным образом выбирается ребро BE,
вес которого равен 7. На этом этапе красным выделено гораздо больше ребер: BC, потому что оно создаст цикл BCE, DE, потому что оно создаст
цикл DEBA, и FE, потому что оно сформирует цикл FEBAD.
Алгоритм завершается добавлением ребра EG
с весом 9.
Минимальное остовное дерево построено построено.

Поиск минимального пути

Алгоритм Флойда-Уоршелла

Алгоритм Флойда-Уоршелла

Восстановление пути в алгоритме Флойда-Уоршелла

Пример
Матрица смежности:

Пример
Матрица 1-расстояний

Пример
1-я итерация

Пример
2-я итерация

Пример
3-я итерация

Пример
4, 5, 6 итерации

Пример
Матрица кратчайших расстояний:

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

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

Пример

Пример

Пример

Пример

Пример

Пример

Пример

Пример