Динамический массив и алгоритм дейкстры виндовс форм. Алгоритм дейкстры

Для начала рассмотрим алгоритм Фалкерсона (графический способ упорядочивания элементов):

• 1. Найти вершины графа, в которые не входит не одна дуга. Они образуют первую группу. Пронумеровать вершины группы в произвольном порядке.
• 2. Вычеркнуть все пронумерованные вершины и дуги, из них исходящие. В получившемся графе найдется, по крайней мере, одна вершина, в которую не входит ни одна дуга. Этой вершине, входящей во вторую группу, присвоить очередной номер, и т. д. Второй шаг повторять до тех пор, пока не будут упорядочены все вершины.

Теперь рассмотрим алгоритм нахождения кратчайшего пути между двумя заданными вершинами в ориентированном графе. Пусть G = {S, U, ? } - ориентированный граф со взвешенными дугами. Обозначим s-вершину - начало пути и t-вершину - конец пути.

Алгоритм Дейкстры содержит одно ограничение - веса дуг должны быть положительными. Сам алгоритм состоит из двух этапов. На первом находится длина кратчайшего пути, на втором строится сам путь от вершины s к вершине t.

Этап 1. Нахождение кратчайшего пути.

Шаг 1. Присвоение вершинам начальных меток.

Полагаем d(s)=0* и считаем эту метку постоянной (постоянные метки помечаются сверху звёздочкой). Для остальных вершин x i S, x i ?s полагаем d(x i) = ? и считаем эти метки верными. Пусть x” = s, x” - обозначение текущей вершины.

Шаг 2. Изменение меток.

Для каждой вершины x i с временной меткой, непосредственно следующей за вершиной x”, меняем ее метку в соответствии со следующим правилом:

d нов. (x i) = min{d стар. (x i), d(x”)+щ(x”, x i)}.(1. 6. 1)

Шаг 3. Превращение метки из временной в постоянную.

Из всех вершин с временными метками выбираем вершину x j * с наименьшим значением метки

d(x j *) = min {d(x j) / x j S, d(x j) - временная}. (1. 6. 2)

Превращаем эту метку в постоянную и полагаем x” = x j *.

Шаг 4. Проверка на завершение первого этапа.

Если x” = t, то d(x”) - длина кратчайшего пути от s до t. В противном случае происходит возвращение ко второму шагу.

Этап 2. Построение кратчайшего пути.

Шаг 5. Последовательный поиск дуг кратчайшего пути.

Среди вершин, непосредственно предшествующих вершине x” c постоянными метками, находим вершину x i , удовлетворяющую соотношению

d(x”) = d(x i) + щ(x i , x”).(1. 6. 3)

Включаем дугу (x i , x”) в искомый путь и полагаем x” = x i .

Шаг 6. Проверка на завершение второго этапа.

Если x” = s, то кратчайший путь найден - его образует последовательность дуг, полученных на пятом шаге и выстроенных в обратном порядке. В противном случае возвращаемся к пятому шагу.

Пример 8: Задана весовая матрица? графа G. Найти минимальный путь из вершины x 1 в вершину x6 по алгоритму Дейкстры.

На рисунке 1. 11 изображён сам граф по данной матрице весов. Поскольку на данном графе есть цикл между вершинами x 2 , x 3 и x 5 , то вершины графа нельзя упорядочить по алгоритму Фалкерсона. На рисунке графа временные и постоянные метки указаны над соответствующей вершиной. Итак, распишем подробно работу алгоритма Дейкстры по шагам.

Шаг 1. Полагаем d(x 1) = 0*, x” = x 1 , d(x 2) = d(x 3) = d(x 4) = d(x 5) = d(x 6) = ?.

1-ая итерация.

Шаг 2. Множество вершин, непосредственно следующих за x” = x1 со временными метками S” = {x 2 , x 4 , x 5 }. Пересчитываем временные метки вершин: d(x 2) = min{?, 0*, + 9} = 9, d(x 4) = min{?, 0* + 6} = 6, d(x 5) = min{?, 0* + 11} = 11.

Шаг 3. Одна из временных меток превращается в постоянную min{9, ?, 6, 11, ?} = 6* = d(x 4), x” = x 4 .

Шаг 4. x” = x 4 ? t = x 6 , происходит возвращение на второй шаг.

2-ая итерация.

Шаг 2. S” = {x 2 , x 3 , x 5 }, d(x 2) = min{9, 6* + 5} = 9, d(x 3) = min {?, 6* + 7} = 13, d(x 5) = min{11, 6* + 6} = 11.

Шаг 3. min{d(x 2), d(x 3), d(x 5), d(x 6)} = min{9, 13, 11, ?} = 9* = d(x 2), x” = x 2 .

Шаг 4. x 2 ? x 6 , возвращение на второй шаг.

3-я итерация.

Шаг 2. S” ={x 3 }, d(x 3) = min{13, 9* + 8} = 13.

Шаг 3. min{d(x 3), d(x 5), d(x 6)} = min{31, 11, ?} = 11* = d(x 5), x” = x 5 .

Шаг 4. x 5 ? x 6 , возвращение на второй шаг.

4-ая итерация.

Шаг 2. S”={x 6 }, d(x 6) = min{?, 11* + 4} = 15.

Шаг 3. min {d(x 3), d(x 6)} = min{13, 15} = 13* = d(x 3), x” = x 3 .

Шаг 4. x 3 ? x 6 , возвращение на второй шаг.

5-ая итерация.

Шаг 2. S” = {x 6 }, d(x 6) = min{15, 13* + 9} = 15.

Шаг 3. min{d(x 6) } = min{15} = 15*, x” = x 6 .

Шаг 4. x 6 = t = x 6 , конец первого этапа.

Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x 6 с постоянными метками S” = {x 3 , x 5 }. Проверим для этих двух вершин выполнение равенства d нов. (x i) = min{d стар. (x i), d(x”) + щ(x”, x i)}:

d(x”) = 15 = 11* + 4 = d(x 5) + щ(x 5 , x 6),

d(x”) = 15 ? 13* + 9 = d(x 3) + щ(x 3 , x 6).

Включаем дугу (x 5 , x 6) в кратчайший путь. x” = x 5 .

Шаг 6. x” ? s = x 1 , возвращение на пятый шаг.

2-ая итерация.

Шаг 5. S” = {x 1 , x 4 }.

d(x”) = 11 = 0* + 11 = d(x 1) + щ(x 1 , x 5),

d(x”) = 11 ? 6* + 6 = d(x 4) + щ(x 4 , x 5).

Включаем дугу (x 1 , x 5) в кратчайший путь. x” = x 1 .

Шаг 6. x” = s = x 1 , завершение второго этапа.

Итак, кратчайший путь от вершины x 1 до вершины x 6 построен. Его длина (вес) равна 15, сам путь образует следующая последовательность дуг: м = (x 1 , x 5) - (x 5 , x 6).

Алгоримтм Демйкстры (Dijkstra"s algorithm) - алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием "Сначала Кратчайший Путь" (Shortest Path First).

Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G = (V, E) с исходной вершиной s, в котором веса всех рёбер неотрицательны ((u, v) ? 0 для всех (u, v) E). В случае, когда ребра графа не равны, целесообразно использовать этот алгоритм.

Формулировка задачи. Имеется граф. Некоторая его вершина обозначена как вершина 1. Необходимо найти минимальные пути от вершины 1 до каждой из вершин графа. Минимальным путём будем называть путь с минимальной суммой цен вдоль пути. Ценой назовем неотрицательное число являющееся весом ребра.

Идея алгоритма. Идея основывается на следующем очевидном утверждении: Пусть построен минимальный путь из вершины а в вершину B. И пусть вершина B связана с некоторым количеством вершин i . Обозначим через C i - цену пути из вершины B в вершину i. Выберем из C i минимальную величину. Тогда минимальное продолжение пути из точки B пойдёт через выбранную величину.

Это утверждение действительно не требует доказательства. И из него вытекает очень серьёзное следствие. Пусть есть множество вершин через которые уже проходят минимальные пути. Такое множество гарантированно есть, это вершина 1. Утверждение сформулированное выше даёт возможность добавлять к уже существующему множеству вершин (будем далее называть их выделенными) еще одну вершину, а так как в графе количество вершин конечно, то за конечное количество шагов все вершины графа окажутся выделенными, а это и будет решением.

Сущность алгоритма Дейкстры и заключается в процедуре добавления еще одной вершины к множеству выделенных. Эта процедура состоит из двух шагов:

1. Строим множество вершин инцидентных выделенным и находим среди их вершину с наименьшей ценой. Найденная вершина добавляется в множество выделенных.

2. Строим множество вершин инцидентных выделенным и определяем для них новые цены. Новая цена вершины это минимальная цена пути от множества выделенных вершин до данной вершины. Строится новая цена так:

a. Для невыделенной вершины во множестве выделенных определяется подмножество вершин инцидентных данной.

b. Для каждой вершины выделенной подмножества определяется цена пути до данной.

c. Определяется минимальная цена. Эта цена и становится ценой вершины.

Алгоритм работает с двумя типами цен: ценой ребра и ценой вершины. Цены ребер являются постоянной величиной. Цены же вершин постоянно пересчитываются. Смысл этих цен различен. Цена ребра это цена перехода из вершины в вершину соединённую этим ребром. А цена вершины это цена минимального пути. Ещё одно важное замечание касается пересчета предварительных цен. Фактически, есть смысл пересчитывать предварительные цены только для тех вершин которые связаны с вершиной добавленной во множество выделенных на последнем шаге, так как для других вершин нет причин изменения предварительной цены.

Известно, что все цены (например, прокладки пути или проезда) неотрицательны. Найти наименьшую стоимость пути 1->i для всех i=1. n за время O (n2).

В процессе работы алгоритма некоторые города будут выделенными (в начале - только город 1, в конце - все). При этом:

для каждого выделенного города i хранится наименьшая стоимость пути 1->i; при этом известно, что минимум достигается на пути, проходящем только через выделенные города;

для каждого невыделенного города i хранится наименьшая стоимость пути 1->i, в котором в качестве промежуточных используются только выделенные города.

Множество выделенных городов расширяется на основании следующего замечания: если среди всех невыделенных городов взять тот, для которого хранимое число минимально, то это число является истинной наименьшей стоимостью. В самом деле, пусть есть более короткий путь. Рассмотрим первый невыделенный город на этом пути - уже до него путь длиннее! (Здесь существенна неотрицательность цен.)

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

Другими словами, каждой вершине из V сопоставим метку - минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово - на каждом шаге он "посещает" одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0 , метки остальных вершин - бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из еще не посещенных вершин выбирается вершина u , имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.

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

Опишем более подробно схему работы алгоритма Дейкстры.

Алгоритм использует три массива из N (= числу вершин сети) чисел каждый. Первый массив A содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B содержит расстояния - текущие кратчайшие рас - стояния от до соответствующей вершины; третий массив с содержит номера вершин - k-й элемент С [k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний D задает длины дуге D ; если такой дуги нет, то D присваивается большое число Б, равное "машинной бесконечности".

Теперь можно описать:

1. (инициализация). В цикле от 1 до N заполнить нулями массив A; заполнить числом i массив C; перенести i-ю строку матрицы D в массив B, A [i]: =1; C [i]: =0 (i - номер стартовой вершины)

2. (общий шаг). Hайти минимум среди неотмеченных (т.е. тех k, для которых A [k] =0); пусть минимум достигается на индексе j, т.е. B [j] <=B [k] Затем выполняются следующие операции: A [j]: =1; если B [k] >B [j] +D , то (B [k]: =B [j] +D ; C [k]: =j) (Условие означает, что путь Vi. Vk длиннее, чем путь Vi. Vj Vk). (Если все A [k] отмечены, то длина пути от Vi до Vk равна B [k]. Теперь надо) перечислить вершины, входящие в кратчайший путь).

3. (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке следующей процедурой:)

2. Выдать z;

3. z: =C [z]. Если z = О, то конец, иначе перейти к 3.2.

Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т.е. алгоритм Дейкстры имеет квадратичную сложность: O (n2).

Ниже приведена блок-схема алгоритма Дейкстры (см. рис.2).

Рис.2. Блок-схема алгоритма Дейкстры

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

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

По завершению турнира «Новогодняя ночь» спонсор решил отправить $m$ призерам подарки по почте. Зная количество участников $n$ и время доставки почты между некоторыми отделениями «Укрпочты», найти, через какое минимальное время последний из призеров получит свой приз.

Входные данные

Первая строка содержит $3$ числа: количество участников турнира $n$, количество призов спонсора $m$ и количество известных временных сроков доставки между некоторыми из отделений $k$. В следующей строке через пробел указаны номера участников, ставших призёрами.

Далее идет $k$ строк по $3$ числа в каждой с информацией об известных сроках доставки между некоторыми из отделений в формате: $a$ $b$ $t$, где $a$ и $b$ — номера отделений, $t$ $(0 \leqslant t \leqslant 365)$ — время доставки почты между ними. В последней строке находится единственное число — номер почтового отделения, из которого спонсор будет отправлять призы. Известно, что $1 \leqslant n, m, a, b \leqslant 365$.

Выходные данные

Если все призы будут доставлены участникам — вывести в первой строке «The good sponsor!», а в следующей — время, через какое последний из призеров получит свой приз. Если хотя бы один из участников не сможет получить приз — вывести в единственной строке «It is not fault of sponsor…». Фразы выводить без кавычек.

Тесты

Решить задачу о нахождении кратчайшего пути алгоритмом Дейкстры.
Найти кратчайший путь от Х0 до Х7. Граф задан элементами стоимостной матрицы

Построим этот граф


Начнем с элемента Х0 и присвоим ему метку 0, рассмотрим всех его соседей, т.к. там еще нет пометок, то присвоим им соответствующие длины:


Все соседи Х0 рассмотрены, помечаем ее и переходим к вершине Х1. ЕЕ соседи Х0, Х2,Х4, но Х0 помечена, не рассматриваем ее. Для Х2: , оставляем метку.

Для Х4: , заменяем метку. Все соседи вершины Х1 рассмотрены, помечаем ее


переходим к вершине Х2. ЕЕ соседи Х0, Х1,Х3, Х4, Х5, Х6, но Х0, Х1 помечены, не рассматриваем их.
Для Х3: , оставляем метку.
Для Х5: , заменяем метку.
Для Х4: , оставляем метку.
Для Х6: , заменяем метку.
Все соседи вершины Х2 рассмотрены, помечаем ее.


переходим к вершине Х3. ЕЕ соседи Х0, Х2, Х6, но Х0, Х2 помечены, не рассматриваем их.
Для Х6: , оставляем метку.
Все соседи вершины Х3 рассмотрены, помечаем ее.


переходим к вершине Х4. ЕЕ соседи Х1,Х2, Х5, Х7, но Х1, Х2 помечены, не рассматриваем их.
Для Х5: , заменяем метку.
Для Х7: , заменяем метку.
Все соседи вершины Х4 рассмотрены, помечаем ее.


переходим к вершине Х5. ЕЕ соседи Х2,Х4, Х6, Х7, но Х2, Х4 помечены, не рассматриваем их.
Для Х6: , оставляем метку.
Для Х7: , оставляем метку.
Все соседи вершины Х5 рассмотрены, помечаем ее.


переходим к вершине Х6. ЕЕ соседи Х2,Х3, Х5, Х7, но Х2, Х3, Х5 помечены, не рассматриваем их.
Для Х7: , оставляем метку.
Все соседи вершины Х6 рассмотрены, помечаем ее. И помечаем оставшуюся Х7, все вершины рассмотрены.


Вывод: Кратчайший путь их Х0 в Х7 имеет длину 101, этот путь: Х7-Х4-Х1-Х0.

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

Описание

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

В начале расстояние для начальной вершины полагается равным нулю, а расстояния до всех остальных понимаются бесконечными. Массив флагов, обозначающих то, пройдена ли вершина, заполняется нулями. Затем на каждом шаге цикла ищется вершина с минимальным расстоянием до изначальной и флагом равным нулю. Для неё устанавливается флаг и проверяются все соседние вершины. Если рассчитанное ранее расстояние от исходной вершины до проверяемой больше, чем сумма расстояния до текущей вершины и длины ребра от неё до проверяемой вершины, то расстояние до проверяемой вершины приравниваем к расстоянию до текущей+ребро от текущей до проверяемой. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда расстояние до всех вершин c флагом 0 бесконечно. Последний случай возможен тогда и только тогда, когда граф несвязеный.

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

Вход: С : array of real – матрица длин дуг графа; s – вершина, от которой ищется кратчайший путь и t – вершина, к которой он ищется.

Выход: векторы Т: array of real; и Н: array of 0..р. Если вершина v лежит на кратчайшем пути от s к t, то T[v] - длина кратчайшего пути от s к у; Н[у] - вершина, непосредственно предшествующая у на кратчайшем пути.

Н – массив, в котором вершине n соответствует вершина m, предыдущая на пути к n от s.

T – массив, в котором вершине n соответствует расстояние от неё до s.

X – массив, в котором вершине n соответствует 1, если путь до неё известен, и 0, если нет.

инициализация массивов:

for v from 1 to р do

Т[ v ]: = ∞ { кратчайший путь неизвестен }

X[v]: = 0 { все вершины не отмечены}

H[s]: = 0 { s ничего не предшествует }

T[s] : = 0 { кратчайший путь имеет длину 0...}

X[s] : = 1 { ...и он известен } v : = s { текущая вершина }

М: { обновление пометок }

for и ∈ Г(и ) do

if Х[и] = 0 & Т[и] > T[v] + C then

Т[и] : = T[v] + C { найден более короткий путь из s в и через v }

H[u]: = v { запоминаем его }

m : = ∞

v : = 0

{ поиск конца кратчайшего пути }

for и from 1 to p do

if X[u] = 0 &T[u] < t then

v: = u ;

m: = T[u] { вершина v заканчивает кратчайший путь из s

if v = 0 then

stop { нет пути из s в t } end if

if v = t then

stop { найден кратчайший путь из s в t } end if

X[v]: = 1 { найден кратчайший путь из s в v } goto M

Обоснование

Для доказательства корректности алгоритма Дейкстры достаточно заметить, что при каждом выполнении тела цикла, начинающегося меткой М, в качестве v используется вершина, для которой известен кратчайший путь из вершины s. Другими словами, если X[v] = 1, то T[v] = d(s,v), и все вершины на пути (s,v), определяемом вектором Н, обладают тем же свойством, то есть

Vu Т[и] = 1 => Т[и] = d(s,u)&T] = 1.

Действительно (по индукции), первый раз в качестве v используется вершина s, для которой кратчайший путь пустой и имеет длину 0 (непустые пути не могут быть короче, потому что длины дуг неотрицательны). Пусть Т[u] = d(s,u) для всех ранее помеченных вершин и. Рассмотрим вновь помеченную вершину v , которая выбрана из условия T[v] = min Т[и]. Заметим, что если известен путь, проходящий через помеченные вершины, то тем самым известен кратчайший путь. Допустим (от противного), что T[v]> d(s, v), то есть найденный путь, ведущий из s в v, не является кратчайшим. Тогда на этом пути должны быть непомеченные вершины. Рассмотрим первую вершину w на этом пути, такую что T[w]= 0.Имеем: T[w]= d(s,w)⩽d(s>v) < Т[v],что противоречит выбору вершины u.

Временная сложность

Сложность алгоритма Дейкстры зависит от способа нахождения не посещённой вершины с минимальным расстоянием до изначальной, способа хранения множества непосещённых вершин и способа обновления меток. Пусть n количество вершин, а через m - количество рёбер в графе. Тогда в простейшем случае, когда для поиска вершины с минимальным расстоянием до изначальной вершины просматривается всё множество вершин, а для хранения расстояний используется массив, время работы алгоритма - О(n 2). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству рёбер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма O(n 2 +m), но, так как m много меньше n(n-1), в конечном счёте получается О(n 2).

Для разреженных графов (то есть таких, для которых m много меньше n²) непосещённые вершины можно хранить в двоичной куче, а в качестве ключа использовать значения расстояний. Так как цикл выполняется порядка n раз, а количество релаксаций (смен меток) не больше m, время работы такой реализации - О(nlogn+mlogn)

Пример

Вычисление расстояний от вершины 1 по проходимым вершинам: