5.4.3. Задача о кратчайшем пути и алгоритм Дейкстры ее решения
Пусть задан орграф G
(V
,
E
), каждой дуге
которого поставлено в соответствие
число
,
называемое длиной дуги
.
Определение. Длиной пути называется сумма длин дуг, составляющих этот путь. Задача о кратчайшем пути ставится так.
Вариант 1. Найти длины кратчайших путей (путей минимальной длины) и сами пути от фиксированной вершины s до всех остальных вершин графа.
Вариант 2. Найти длины кратчайших путей и сами пути между всеми парами вершин данного графа.
Если в графе имеются дуги отрицательной
длины, задача может не иметь решений
(потеряет смысл). Это происходит из-за
того, что в графе может присутствовать
контур отрицательной длины. Наличие
контуров отрицательной длины означает,
что длину пути можно сделать равной
.
А если контуров отрицательной длины
нет, то кратчайшие пути существуют и
любой кратчайший путь – это простая
цепь.
Заметим, что если кратчайший путь существует, то любой его подпуть – это тоже кратчайший путь между соответствующими вершинами.
Алгоритм Дейкстры решения задачи о кратчайшем пути.
Алгоритм работает с дугами положительной длины и определяет кратчайшие пути от фиксированной вершины s до всех остальных вершин графа. Обозначим эти вершины v 1 , v 2 ,…, v n .
Определение. Назовем вершину 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 ;
кратчайший путь до очередной упорядоченной вершины может проходить только через уже упорядоченные вершины.
Пусть алгоритм уже упорядочил вершины
v
1 ,
v
2 …
v
k
.
Обозначим через
,
длину кратчайшего пути до вершины v
i
.
Рассмотрим все дуги исходного графа,
которые начинаются в одной из вершин
множества
и оканчиваются в еще неупорядоченных
вершинах. Для каждой такой дуги, например
,
вычислим сумму
.
Эта сумма равна длине пути из s
в y
, в котором вершина
v
i
есть предпоследняя вершина, а путь из
s
в v
i
– кратчайший из всех путей, соединяющих
s
и v
i
.
Этим самым определены длины всех путей
из s
в еще не упорядоченные
вершины, в которых промежуточными
вершинами являются только вершины из
числа k
ближайших к
s
. Пусть кратчайший
из этих путей оканчивается на вершине
w
. Тогда w
и есть
по близости к s
вершина.
Технически действия по алгоритму
Дейкстры осуществляются при помощи
аппарата меток вершин. Метка вершины v
обозначается как
.
Всякая метка – это число, равное длине
некоторого пути от s
до v
. Метки делятся
на временные и постоянные. На каждом
шаге только одна метка становиться
постоянной. Это означает, что ее значение
равно длине кратчайшего пути до
соответствующей вершины, а сама эта
вершина упорядочивается. Номер очередной
упорядоченной вершины обозначим буквой
р
.
Описание алгоритма .
Шаг 1.
(Начальная установка)
.
Положить
и считать эту метку постоянной. Положить
,
и считать эти метки временными.
Положить
.
Шаг 2. (Общий шаг). Он повторяется n раз, пока не будут упорядочены все вершины графа.
Пересчитать временную метку
всякой неупорядоченной вершины v
i
,
в которую входит дуга, выходящая из
вершины р,
по правилу
Выбрать вершину с минимальной временной меткой. Если таких вершин несколько, выбрать любую.
Пусть w
-
вершина
с минимальной временной меткой. Считать
метку
постоянной и положить
.
Шаги алгоритма Дейкстры удобно оформлять в таблице, каждый столбец которой соответствует вершине графа. Строки таблицы соответствуют повторению общего шага.
Пример
.
Для графа на рис. 4. найти
кратчайшие пути от вершин
до всех остальных вершин графа. Ребра
означают две разнонаправленные дуги
одинаковой длины.
Решение. В табл. 1 записаны метки вершин на каждом шаге. Постоянные метки помечены знаком «+». Подробно опишем, как вычисляются метки вершин.
Из вершины 1 выходят дуги в вершины 2, 5, 6. Пересчитываем метки этих вершин и заполним вторую строку таблицы.
Метка вершины 6 становиться постоянной,
.
Из вершины 6 выходят дуги в еще неупорядоченные вершины 2, 5, 8, 9. Пересчитываем их временные метки
Заполняем 3 строку таблицы. Минимальная
из временных меток равна 3 (метка вершины
9),
.
Из вершины 9 выходят дуги в еще неупорядоченные вершины 5, 8, 11, 12. Тогда
Заполняем четвертую строку таблицы. В этой строке две вершины 2 и 12 имеют минимальные временные метки, равные 4. Сначала упорядочим, например, вершину 2. Тогда на следующем шаге будет упорядочена вершина 12.
Таблица 1
.
Из вершины 2 выходят дуги в еще неупорядоченные вершины 3, 4, 5. Пересчитываем временные метки этих вершин
Заполняем 5 строку таблицы. Минимальная
из временных меток равна 4 (метка вершины
12),
.
Заполняем 6 строку таблицы. Минимальная
из временных меток равна 5 (метка вершины
5),
.
Заполняем 7 строку таблицы. Становиться
постоянной метка вершины 8 (она равна
5),
.
Вершина 11 упорядочивается.
Из вершины 11 выходят дуги в неупорядоченные вершины 7, 10. Пересчитываем временные метки этих вершин
Вершина 4 получает постоянную метку.
Из вершины 4 выходят дуги в неупорядоченные вершины 3, 7. Пересчитываем временные метки
Упорядочиваем вершину 3.
Заполняем 12 строку таблицы. На этом шаге упорядочиваем последнюю неупорядоченную вершину 10.
Построение дерева кратчайших путей.
Дерево кратчайших путей – это ориентированное дерево с корнем в вершине S . Все пути в этом дереве – кратчайшие для данного графа.
Дерево кратчайших путей строится по таблице, в него включаются вершина за вершиной в том порядке, в котором они получали постоянные метки. Первым в дерево включается корень – вершина S .
Построим дерево кратчайших путей для нашего примера.
Сначала включаем в дерево корень –
вершину 1. Затем в дерево включается
дуга (1,6). Следующей была упорядочена
вершина 9, длина кратчайшего пути до
которой равна 3. Первый раз число 3
появилось в третьей строке, которая
заполнялась при
.
Следовательно, вершина 6 – предпоследняя
вершина кратчайшего пути до вершины 9.
Включаем в дерево дугу (6,9) длины 1.
Затем была упорядочена вершина 2 с длиной
кратчайшего пути, равной 4. Это число
первый раз появилось в третьей строке,
которая заполнялась при
.
Следовательно, кратчайший путь во вторую
вершину проходит по дуге (6,2). Включаем
в дерево дугу (6,2) длины 2.
Далее была упорядочена вершина 12,
.
Первый раз число 4 появляется в четвертой
строке, которая заполнялась при
.
В дерево включается дуга (9,12) длины 1.
Полное дерево кратчайших путей показано
на рис. 5.
Алгоритм Дейкстры может ошибаться, если в графе есть дуги отрицательной длины. Так, отыскивая кратчайшие пути от вершины s =1 для графа на рис. 6, алгоритм сначала упорядочит вершину 3, затем вершину 2 и закончит работу. При этом этот кратчайший путь до вершины 3, с точки зрения алгоритма Дейкстры, это дуга (1,3) длины 3.
На самом деле, кратчайший путь до вершины 3 состоит из дуг (1,2) и (2,3), длина этого пути равна 5+(-3)=2.
Из-за наличия дуги (2,3) отрицательной длины –3 оказались нарушенными следующие базовые принципы:
ближайшая к s вершина лежит от нее на расстоянии двух дуг, а не одной;
промежуточная вершина кратчайшего пути 1-2-3 (вершина 2) лежит дальше от вершины 1 (на расстоянии 5), чем конечная вершина пути 3.
Следовательно, присутствие дуг отрицательной длины усложняет решение задачи о кратчайшем пути и требует использования более сложных алгоритмов, нежели алгоритм Дейкстры.
Алгоритм Дейкстры – алгоритм на графах, который находит кратчайший путь между двумя данными вершинами в графе с неотрицательными длинами дуг. Также часто ставится задача расчёта кратчайшего пути от данной вершины до всех остальных. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации.
Описание
На вход алгоритма подаётся взвешенный ориентированный граф с дугами неотрицательного веса. На выходе получается набор кратчайших путей от данной вершины до других.
В начале расстояние для начальной вершины полагается равным нулю, а расстояния до всех остальных понимаются бесконечными. Массив флагов, обозначающих то, пройдена ли вершина, заполняется нулями. Затем на каждом шаге цикла ищется вершина с минимальным расстоянием до изначальной и флагом равным нулю. Для неё устанавливается флаг и проверяются все соседние вершины. Если рассчитанное ранее расстояние от исходной вершины до проверяемой больше, чем сумма расстояния до текущей вершины и длины ребра от неё до проверяемой вершины, то расстояние до проверяемой вершины приравниваем к расстоянию до текущей+ребро от текущей до проверяемой. Цикл завершается, когда флаги всех вершин становятся равны 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 по проходимым вершинам:
Алгоритм Дейкстры предназначен для нахождения кратчайшего пути между вершинами в неориентированном графе.
Идея алгоритма следующая: сначала выберем путь до начальной вершины равным нулю и заносим эту вершину во множество уже выбранных, расстояние от которых до оставшихся невыбранных вершин определено. На каждом следующем этапе находим следующую выбранную вершину, расстояние до которой наименьшее, и соединенную ребром с какой-нибудь вершиной из множества невыбранных (это расстояние будет равно расстоянию до выбранной вершины плюс длина ребра).
Пример 1. Найти кратчайший путь на графе от вершины L до вершины D (рис. 10.7).
Рис. 10.7.
Запишем алгоритм в виде последовательности шагов (табл. 10.1). Шаг 1. Определяем расстояния от начальной вершины L до всех остальных.
Таблица 10.1
Метод Дейкстры (первый шаг)
Выбранная |
Путь до выбранной вершины |
Невыбранная вершина |
|||||||
Шаг 2. Выбираем наименьшее расстояние от L до В; найденная вершина В принимается за вновь выбранную. Найденное наименьшее расстояние добавляем к длинам ребер от новой вершины В до всех остальных. Выбираем минимальное расстояние от В до N. Новую вершину N принимаем за выбранную (табл. 10.2).
Таблица 10.2
Метод Дейкстры (второй шаг)
Выбранная |
Путь до выбранной вершины |
Невыбранная вершина |
|||||||
Для наглядности в дальнейшем вместо знака оо будем ставить знак « - ».
Шаг 3. Определяем расстояния от вершины N л о всех оставшихся (за исключением L и В), как показано в табл. 10.3.
Таблица 10.3
Метод Дейкстры (третий шаг)
Выбранная |
Путь до выбранной вершины |
Невыбранная вершина |
|||||||
Расстояние от вершины L через вершину N до вершины G равно 18 условных единиц. Это расстояние больше, чем расстояние LB + BG = 16 условных единиц, вследствие чего оно не учитывается в дальнейшем. Продолжая аналогичные построения, составим табл. 10.4. Таким образом, найдена длина кратчайшего пути между вершинами L и D (44 условных единицы).
Траекторию пути определяем следующим образом. Выполняем обратный просмотр от конечной вершины к начальной. Просматриваем столбец, соответствующий вершине, снизу вверх и фиксируем первое появление минимальной величины. В столбце, соответствующем вершине D, впервые минимальная длина 44 условных единицы появилась снизу в четвертой строке. В этой строке указана вершина S, к которой следует перейти, т.е. следующим нужно рассматривать столбец, соответствующий вершине S.
Таблица 10.4
Выбранная вершина |
Путь до выбранной вершины |
Невыбранная вершина |
|||||||
В этом столбце минимальная длина, равная 27 условным единицам, указывает следующую вершину G, к которой надлежит перейти, и т.д. Таким образом, получаем траекторию пути: (L, В, G, S, D).
Пример 8. Найти кратчайший путь на графе между 1-й и 7-й вершинами (рис. 10.8).
Определяем (табл. 10.5) следующую выбранную вершину, расстояние до которой наименьшее и соединенную ребром с одной из вершин, принадлежащих множеству невыбранных (это расстояние будет равно расстоянию до выбранной вершины плюс длина ребра).
Рис. 10.8. Граф (а) и соответствующая ему матрица смежности (б)
Табличная реализация метода Дейкстры
Таблица 10.5
Выбранная |
Путь до выбранной вершины |
Невыбранная вершина |
||||||
у 6 |
||||||||
Выполняем обратный просмотр от конечной вершины к начальной.
Просматриваем столбец, соответствующий вершине, снизу вверх и фиксируем первое появление минимальной величины. Кратчайший путь при этом будет равен (V 7 - V 5 - V 2 - У {).
и КОНТРОЛЬНЫЕ ВОПРОСЫ
- 1. Какова теоретическая сложность алгоритмов: построения дерева решений, динамического программирования и Дейкстры?
- 2. В чем особенность использования дерева решений для ориентированного и неорентированного графа?
- 3. В решении каких прикладных задач используются алгоритмы определения в графе кратчайших расстояний между заданными вершинами?
- 4. Может ли быть применен рассмотренный в работе алгоритм Дейкстры к определению кратчайшего расстояния в ориентированном графе?
- 5. Как работает алгоритм Дейкстры?
- 6. Как работает алгоритм динамического программирования применительно к задаче определения в графе кратчайших расстояний между вершинами?
До каждого города области (если двигаться можно только по дорогам).
Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула .
Формальное определение
Пример
Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке.
Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.
Реализации на языках программирования
Исполнение в языке С(Си)
#define SIZE 6 #define INF 1000000000 int a [ SIZE ][ SIZE ] = {{ INF , 5 , INF , INF , INF , INF },{ 1 , 2 , 3 , 4 , 5 , 6 }, // матрица путей { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }, // индексы по горизонтали из точки { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // по вертикали в точку, значение - вес int d [ SIZE ]; // массив найденных кратчайших путей, индексы - вершины графа void deikstra () { int v [ SIZE ]; // массив меток int temp , i ; int minindex , min ; for (i = 0 ; i < SIZE ; i ++ ) { d [ i ] = INF ; // массив путей инициализируется бесконечностью v [ i ] = 1 ; } d [ 0 ] = 0 ; do { // исполнение алгоритма minindex = INF ; min = INF ; for (i = 0 ; i < SIZE ; i ++ ) { if ((v [ i ] == 1 ) && (d [ i ] < min )) { min = d [ i ]; minindex = i ; } } if (minindex != INF ) { for (i = 0 ; i < SIZE ; i ++ ) { if (a [ minindex ][ i ] > 0 ) { temp = min + a [ minindex ][ i ]; if (temp < d [ i ]) d [ i ] = temp ; } } v [ minindex ] = 0 ; } } while (minindex < INF ); }
Алгоритм Дейкстры (англ. Dijkstra’s algorithm) - алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.
Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке.
Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.
Кружками обозначены вершины, линиями - пути между ними (рёбра графа). В кружках обозначены номера вершин, над рёбрами обозначена их «цена» - длина пути. Рядом с каждой вершиной красным обозначена метка - длина кратчайшего пути в эту вершину из вершины 1.
Первый шаг . Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.
Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме значения метки вершины 1 и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.
Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й.
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.
Второй шаг . Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещённых вершин. Это вершина 2 с меткой 7.
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.
Первый (по порядку) сосед вершины 2 - вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.
Следующий сосед вершины 2 - вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а это меньше 17, поэтому метка не меняется.
Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-й вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку 22<, устанавливаем метку вершины 4 равной 22.
Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещённую.
Третий шаг . Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:
Дальнейшие шаги . Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.
Завершение выполнения алгоритма . Алгоритм заканчивает работу, когда нельзя больше обработать ни одной вершины. В данном примере все вершины зачёркнуты, однако ошибочно полагать, что так будет в любом примере - некоторые вершины могут остаться незачёркнутыми, если до них нельзя добраться, т. е. если граф несвязный. Результат работы алгоритма виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.
Реализация алгоритма на различных языках программирования:
C++
#include "stdafx.h" #includePascal
program DijkstraAlgorithm; uses crt; const V=6; inf=100000; type vektor=array of integer; var start: integer; const GR: array of integer=((0, 1, 4, 0, 2, 0), (0, 0, 0, 9, 0, 0), (4, 0, 0, 7, 0, 0), (0, 9, 7, 0, 0, 2), (0, 0, 0, 0, 0, 8), (0, 0, 0, 0, 0, 0)); {алгоритм Дейкстры} procedure Dijkstra(GR: array of integer; st: integer); var count, index, i, u, m, min: integer; distance: vektor; visited: array of boolean; begin m:=st; for i:=1 to V do begin distance[i]:=inf; visited[i]:=false; end; distance:=0; for count:=1 to V-1 do begin min:=inf; for i:=1 to V do if (not visited[i]) and (distance[i]<=min) then begin min:=distance[i]; index:=i; end; u:=index; visited[u]:=true; for i:=1 to V do if (not visited[i]) and (GR<>0) and (distance[u]<>inf) and (distance[u]+GRJava
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Solution { private static int INF = Integer.MAX_VALUE / 2; private int n; //количество вершин в орграфе private int m; //количествое дуг в орграфе private ArrayListЕщё один вариант:
Import java.io.*;
import java.util.*;
public class Dijkstra {
private static final Graph.Edge GRAPH = {
new Graph.Edge("a", "b", 7),
new Graph.Edge("a", "c", 9),
new Graph.Edge("a", "f", 14),
new Graph.Edge("b", "c", 10),
new Graph.Edge("b", "d", 15),
new Graph.Edge("c", "d", 11),
new Graph.Edge("c", "f", 2),
new Graph.Edge("d", "e", 6),
new Graph.Edge("e", "f", 9),
};
private static final String START = "a";
private static final String END = "e";
public static void main(String args) {
Graph g = new Graph(GRAPH);
g.dijkstra(START);
g.printPath(END);
//g.printAllPaths();
}
}
class Graph {
private final Map