Сложность алгоритма дейкстры. Нахождение кратчайших путей. Алгоритм Дейкстры. Схема реализации последовательного алгоритма

Dijkstra

> q; for (int i = 0; i < n; ++i) { q.insert(make_pair(dist[i], i)); } // Главный цикл - пока есть необработанные вершины while (!q.empty()) { // Достаем вершину с минимальным расстоянием pair < (int)edges.size(); ++i) { // Делаем релаксацию if (dist[i].first] > cur.first + edges[i].second) { q.erase(make_pair(dist[i].first], edges[i].first)); dist[i].first] = cur.first + edges[i].second; q.insert(make_pair(dist[i].first], edges[i].first)); } } } }

Доказательство корректности

• Пусть найденное алгоритмом dist"[w] < dist[v]. Тогда рассмотрим последнюю релаксацию ребра, ведущего в v: (s, v). Расстояние до s было подсчитано верно, значит, существует путь из u в v веса dist[s] + w = dist"[v] < dist[v]. Противоречие
• Пусть найденное алгоритмом dist"[w] > dist[v]. Тогда рассмотрим момент обработки вершины w. В этот момент было релаксировано ребро (w, v), и, соответственно, текущая оценка расстояния до вершины v стала равной dist[v], а в ходе следующих релаксаций она не могла уменьшиться. Противоречие

Сложность алгоритма

Но при чем же здесь задача с собеседования в Twitter?

Новая постановка задачи с собеседования

• Назовем задачу с собеседования «одномерной». Тогда в k-мерном аналоге будут столбики, пронумерованные k числами, для каждого из которых известна высота. Вода может стекать со столбика в соседний столбик меньшей высоты, либо за край.
• Что такое «соседние столбики»? Пусть у каждого столбика есть свой список соседей, какой угодно. Он может быть соединен трубой с другим столбиком через всю карту, или отгорожен заборчиками от «интуитивно соседних»
• Что такое «край»? Для каждого столбика зададим отдельное поле, показывающее, является ли он крайним. Может, у нас дырка в середине поля?

Теперь решим эту задачу, причем сложность решения будет O(N log N)

• Вершинами будут столбики (и плюс еще одна фиктивная вершина, находящаяся «за краем»).
• Две вершины будут соединены ребром, если в нашей системе они соседние (или если одна из этих вершин - «край», в другая - крайний столбик)
• Вес ребра будет равен максимуму из высот двух столбиков, которые он соединяет

Реализация

void Dijkstra(int v) { // Инициализация int n = (int)edges.size(); dist.assign(n, INF); dist[v] = 0; set > q; for (int i = 0; i > n; ++i) { q.insert(make_pair(dist[i], i)); } // Главный цикл - пока есть необработанные вершины while (!q.empty()) { // Достаем вершину с минимальным расстоянием pair cur = *q.begin(); q.erase(q.begin()); // Проверяем всех ее соседей for (int i = 0; i < (int)edges.size(); ++i) { // Делаем релаксацию if (dist[i].first] > max(cur.first, edges[i].second)) { q.erase(make_pair(dist[i].first], edges[i].first)); dist[i].first] = max(cur.first, edges[i].second); q.insert(make_pair(dist[i].first], edges[i].first)); } } } }

Но это же сложнее и дольше, чем оригинальное решение! Кому это вообще нужно?!

Была ли эта задача хорошей?

Скрытый текст

Если человек хоть немного разбирается в графах, он точно знает алгоритм Дейкстры - он один из самых первых и простых. Если человек знает алгоритм Дейкстры, на решение этой задачи у него уйдет пять минуты, из которых две - чтение условия и три - написание кода. Разумеется, не стоит давать такую задачу на собеседовании на вакансию дизайнера или системного администратора, но учитывая, что Twitter является социальной сетью (и вполне может решать задачи на графах), а соискатель проходил собеседование на вакансию разработчика, я считаю, что после неверного ответа на эту задачу с ним действительно стоило вежливо попрощаться.
Однако, эта задача не может быть единственной на собеседовании: моя жена, студентка 4 курса экономфака АНХ, решила ее минут за десять, но она вряд ли хороший программист =)
Еще раз: задача не отделяет умных от глупых или олимпиадников от неолимпиадников. Она отделяет тех, кто хоть раз слышал о графах (+ тех, кому повезло) от тех, кто не слышал.
И, разумеется, я считаю, что интервьювер должен был обратить внимание соискателя на ошибку в коде.

PS

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

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

Пример 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

Выполняем обратный просмотр от конечной вершины к начальной.

Просматриваем столбец, соответствующий вершине, снизу вверх и фиксируем первое появление минимальной величины. Кратчайший путь при этом будет равен (V 7 - V 5 - V 2 - У {).

и КОНТРОЛЬНЫЕ ВОПРОСЫ

• 1. Какова теоретическая сложность алгоритмов: построения дерева решений, динамического программирования и Дейкстры?
• 2. В чем особенность использования дерева решений для ориентированного и неорентированного графа?
• 3. В решении каких прикладных задач используются алгоритмы определения в графе кратчайших расстояний между заданными вершинами?
• 4. Может ли быть применен рассмотренный в работе алгоритм Дейкстры к определению кратчайшего расстояния в ориентированном графе?
• 5. Как работает алгоритм Дейкстры?
• 6. Как работает алгоритм динамического программирования применительно к задаче определения в графе кратчайших расстояний между вершинами?

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

• 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).

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

Рассмотрим три наиболее эффективных алгоритма нахождения кратчайшего пути :

• алгоритм Дейкстры ;
• алгоритм Флойда ;
• переборные алгоритмы.

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

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

Данный алгоритм является алгоритмом на графах, который изобретен нидерландским ученым Э. Дейкстрой в 1959 году. Алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных и работает только для графов без ребер отрицательного веса.

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

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

Шаг 1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине – 0.

Шаг 2. Все вершины не выделены.

Шаг 3. Первая вершина объявляется текущей.

Шаг 4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра , соединяющего текущую вершину с невыделенной.

Шаг 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход . Иначе, текущей становится найденная вершина . Она же выделяется.

Шаг 6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины.

Шаг 7. Переход на шаг 4.

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

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

Для определения самого

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

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

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначен их вес – длина пути. Рядом с каждой вершиной красным обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.

Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале — бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Первый шаг

Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.

Первый сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7.


Аналогично находим длины пути для всех других соседей (вершины 3 и 6).

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.

Второй шаг

Шаг 1 алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Вершина 1 уже посещена. Следующий сосед вершины 2 - вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9 < 17, поэтому метка не меняется.


Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна 22 (7 + 15 = 22). Поскольку 22<10000, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, помечаем её как посещенную.

Третий шаг

Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим следующие результаты.

Четвертый шаг

Пятый шаг

Шестой шаг

Таким образом, кратчайшим путем из вершины 1 в вершину 5 будет путь через вершины 1 — 3 — 6 — 5 , поскольку таким путем мы набираем минимальный вес, равный 20.

Займемся выводом кратчайшего пути. Мы знаем длину пути для каждой вершины, и теперь будем рассматривать вершины с конца. Рассматриваем конечную вершину (в данном случае — вершина 5 ), и для всех вершин, с которой она связана, находим длину пути, вычитая вес соответствующего ребра из длины пути конечной вершины.
Так, вершина 5 имеет длину пути 20 . Она связана с вершинами 6 и 4 .
Для вершины 6 получим вес 20 — 9 = 11 (совпал) .
Для вершины 4 получим вес 20 — 6 = 14 (не совпал) .
Если в результате мы получим значение, которое совпадает с длиной пути рассматриваемой вершины (в данном случае — вершина 6 ), то именно из нее был осуществлен переход в конечную вершину. Отмечаем эту вершину на искомом пути.
Далее определяем ребро, через которое мы попали в вершину 6 . И так пока не дойдем до начала.
Если в результате такого обхода у нас на каком-то шаге совпадут значения для нескольких вершин, то можно взять любую из них — несколько путей будут иметь одинаковую длину.

Реализация алгоритма Дейкстры

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

Реализация на C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define SIZE 6
int main()
{
int a; // матрица связей
int d; // минимальное расстояние
int v; // посещенные вершины
int temp, minindex, min;
int begin_index = 0;
system("chcp 1251" );
system("cls" );
// Инициализация матрицы связей
for (int i = 0; i {
a[i][i] = 0;
for (int j = i + 1; j printf("Введите расстояние %d - %d: " , i + 1, j + 1);
scanf("%d" , &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
// Вывод матрицы связей
for (int i = 0; i {
for (int j = 0; j printf("%5d " , a[i][j]);
printf("\n" );
}
//Инициализация вершин и расстояний
for (int i = 0; i {
d[i] = 10000;
v[i] = 1;
}
d = 0;
// Шаг алгоритма
do {
minindex = 10000;
min = 10000;
for (int i = 0; i { // Если вершину ещё не обошли и вес меньше min
if ((v[i] == 1) && (d[i] { // Переприсваиваем значения
min = d[i];
minindex = i;
}
}
// Добавляем найденный минимальный вес
// к текущему весу вершины
// и сравниваем с текущим минимальным весом вершины
if (minindex != 10000)
{
for (int i = 0; i {
if (a[i] > 0)
{
temp = min + a[i];
if (temp < d[i])
{
d[i] = temp;
}
}
}
v = 0;
}
} while (minindex < 10000);
// Вывод кратчайших расстояний до вершин
printf("\nКратчайшие расстояния до вершин: \n" );
for (int i = 0; i printf("%5d " , d[i]);

// Восстановление пути
int ver; // массив посещенных вершин
int end = 4; // индекс конечной вершины = 5 - 1
ver = end + 1; // начальный элемент - конечная вершина
int k = 1; // индекс предыдущей вершины
int weight = d; // вес конечной вершины

while (end != begin_index) // пока не дошли до начальной вершины
{
for (int i = 0; i// просматриваем все вершины
if (a[i] != 0) // если связь есть
{
int temp = weight - a[i]; // определяем вес пути из предыдущей вершины
if (temp == d[i]) // если вес совпал с рассчитанным
{ // значит из этой вершины и был переход
weight = temp; // сохраняем новый вес
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
k++;
}
}
}
// Вывод пути (начальная вершина оказалась в конце массива из k элементов)
printf("\nВывод кратчайшего пути\n" );
for (int i = k - 1; i >= 0; i--)
printf("%3d " , ver[i]);
getchar(); getchar();
return 0;
}