Задача о кратчайшем пути и алгоритм Дейкстры ее решения
Ориентированные деревья
Деревья
До 4 баллов за конспект
Определение. Деревомназывают связный граф без циклов. Лесом называют граф без циклов.
На рис. 3 показан лес, состоящий из четырех деревьев.
Можно показать, что число ребер q во всяком дереве с p вершинами равно
p –1.
Определение. Ориентированным деревом (или ордеревом) называется ориентированный граф без циклов, во все вершины которого, кроме одной, входит ровно одна дуга. Единственная вершина, из которой дуги только выходят, называется корнем дерева. Остальные вершины называются узлами дерева.
Из определения дерева следует, что корень связан единственным путем с любой другой вершиной дерева.
На рис. 6 показано ориентированное дерево.
Замечание. При изображении ориентированных деревьев принято помещать корень наверху и все стрелки дуг ориентировать сверху вниз, что избавляет от необходимости изображать эти стрелки.
На рис. 7 показано дерево с рис. 6, изображенное в соответствии с этими правилами. Вершины дерева разбиты на 4 яруса. Нулевой ярус содержит корень дерева. В первом и втором ярусах по 4 вершины, в третьем ярусе 8 вершин.
Пусть задан орграф G(V, E), каждой дуге которого поставлено в соответствие число , называемое длиной дуги.
Определение. Длиной пути называется сумма длин дуг, составляющих этот путь. Задача о кратчайшем путиставится так.
Вариант 1. Найти длины кратчайших путей (путей минимальной длины) и сами пути от фиксированной вершины s до всех остальных вершин графа.
Вариант 2. Найти длины кратчайших путей и сами пути между всеми парами вершин данного графа.
Если в графе имеются дуги отрицательной длины, задача может не иметь решений (потеряет смысл). Это происходит из-за того, что в графе может присутствовать контур отрицательной длины. Наличие контуров отрицательной длины означает, что длину пути можно сделать равной . А если контуров отрицательной длины нет, то кратчайшие пути существуют и любой кратчайший путь – это простая цепь.
Заметим, что если кратчайший путь существует, то любой его подпуть – это тоже кратчайший путь между соответствующими вершинами.
Алгоритм работает с дугами положительной длины и определяет кратчайшие пути от фиксированной вершины s до всех остальных вершин графа. Обозначим эти вершины v1,v2,…,vn .
Определение. Назовем вершину u лежащей ближе к вершине s, чем вершина v, если длина кратчайшего пути от s до u меньше длины кратчайшего пути от s до v. Будем говорить, что вершины u и vравноудалены от вершины s, если длины кратчайших путей от s до u и от s до v совпадают.
Алгоритм Дейкстры последовательно упорядочивает вершины графа в смысле близости к вершине s и основан на следующих базовых принципах.
Если длины дуг – положительные числа, то
ü ближайшая к s вершина – она сама. Длина кратчайшего пути от s до s равна 0;
ü ближайшая к s вершина, отличная от s, лежит от s на расстоянии одной дуги - самой короткой из всех дуг, выходящих из вершины s;
ü любая промежуточная вершина кратчайшего пути от s до некоторой вершины v лежит ближе к s, чем конечная вершина v;
ü кратчайший путь до очередной упорядоченной вершины может проходить только через уже упорядоченные вершины.
Пусть алгоритм уже упорядочил вершины v1,v2… vk. Обозначим через , длину кратчайшего пути до вершины vi.
Рассмотрим все дуги исходного графа, которые начинаются в одной из вершин множества и оканчиваются в еще неупорядоченных вершинах. Для каждой такой дуги, например , вычислим сумму . Эта сумма равна длине пути из s в y, в котором вершина vi есть предпоследняя вершина, а путь из s в vi – кратчайший из всех путей, соединяющих s и vi.
Этим самым определены длины всех путей из s в еще не упорядоченные вершины, в которых промежуточными вершинами являются только вершины из числа k ближайших к s. Пусть кратчайший из этих путей оканчивается на вершине w. Тогда w и есть по близости к s вершина.
Технически действия по алгоритму Дейкстры осуществляются при помощи аппарата меток вершин. Метка вершины v обозначается как . Всякая метка – это число, равное длине некоторого пути от s до v. Метки делятся на временные и постоянные. На каждом шаге только одна метка становиться постоянной. Это означает, что ее значение равно длине кратчайшего пути до соответствующей вершины, а сама эта вершина упорядочивается. Номер очередной упорядоченной вершины обозначим буквой р.
Описание алгоритма.
Шаг 1. (Начальная установка). Положить и считать эту метку постоянной. Положить , и считать эти метки временными. Положить .
Шаг 2. (Общий шаг). Он повторяется n раз, пока не будут упорядочены все вершины графа.
Пересчитать временную метку всякой неупорядоченной вершины vi, в которую входит дуга, выходящая из вершины р, по правилу
Выбрать вершину с минимальной временной меткой. Если таких вершин несколько, выбрать любую.
Пусть w- вершина с минимальной временной меткой. Считать метку постоянной и положить .
Шаги алгоритма Дейкстры удобно оформлять в таблице, каждый столбец которой соответствует вершине графа. Строки таблицы соответствуют повторению общего шага.
Пример.Для графа на рис. 4. найти кратчайшие пути от вершин до всех остальных вершин графа. Ребра означают две разнонаправленные дуги одинаковой длины.
Решение. В табл. 1 записаны метки вершин на каждом шаге. Постоянные метки помечены знаком «+». Подробно опишем, как вычисляются метки вершин.
1. Из вершины 1 выходят дуги в вершины 2, 5, 6. Пересчитываем метки этих вершин и заполним вторую строку таблицы.
; ; .
Метка вершины 6 становиться постоянной, .
2. Из вершины 6 выходят дуги в еще неупорядоченные вершины 2, 5, 8, 9. Пересчитываем их временные метки
; ;
; .
Заполняем 3 строку таблицы. Минимальная из временных меток равна 3 (метка вершины 9), .
3. Из вершины 9 выходят дуги в еще неупорядоченные вершины 5, 8, 11, 12. Тогда
; ;
; .
Заполняем четвертую строку таблицы. В этой строке две вершины - 2 и 12 имеют минимальные временные метки, равные 4. Сначала упорядочим, например, вершину 2. Тогда на следующем шаге будет упорядочена вершина 12.
Таблица 1
p=1
p=6
p=9
p=2
p=12
p=5
p=8
p=11
p=4
p=3
p=7
0+
p=10
Итак, .
4. Из вершины 2 выходят дуги в еще неупорядоченные вершины 3, 4, 5. Пересчитываем временные метки этих вершин
; ; .
Заполняем 5 строку таблицы. Минимальная из временных меток равна 4 (метка вершины 12), .
5. Из вершины 12 выходят дуги в еще неупорядоченные вершины 8, 11, ; .
Заполняем 6 строку таблицы. Минимальная из временных меток равна 5 (метка вершины 5), .
6. Из вершины 5 выходят дуги в еще неупорядоченные вершины 3, 4, 7, 8, ; ; ;
.
Заполняем 7 строку таблицы. Становиться постоянной метка вершины 8 (она равна 5), .
7. Из вершины 8 выходят дуги в неупорядоченные вершины 4, 7, 10, 11. Следовательно, ; ; ; .
Вершина 11 упорядочивается.
8. Из вершины 11 выходят дуги в неупорядоченные вершины 7, 10. Пересчитываем временные метки этих вершин
; .
Вершина 4 получает постоянную метку.
9. Из вершины 4 выходят дуги в неупорядоченные вершины 3, 7. Пересчитываем временные метки
; .
Упорядочиваем вершину 3.
10. Из вершины 3 выходят дуги, входящие в уже упорядоченные вершины. Ни одну метку изменить нельзя. Одиннадцатая строка таблицы повторяет десятую. А минимальная из временных меток - это метка вершины 7, поэтому .
11. Из вершины 7 выходит дуга в неупорядоченную вершину 10,
.
Заполняем 12 строку таблицы. На этом шаге упорядочиваем последнюю неупорядоченную вершину 10.
