Алгоритмы поиска кратчайшего пути

путей до всех вершин
План:

в соответствие некоторое число (вес).
Взвешенными графами могут быть схемы в

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

короткого пути (цепи) между двумя точками (вершинами) на графе, в

которой минимизируется сумма весов рёбер, составляющих путь.

в GPS-навигаторах осуществляется поиск кратчайшего пути между двумя перекрестками. В качестве вершин выступают перекрестки, а дороги являются ребрами, которые лежат между ними. Если сумма длин дорог между перекрестками минимальна, тогда найденный путь самый короткий.

Требуется найти кратчайший путь в заданную вершину назначения t, который

начинается в каждой из вершин графа (кроме t).

Задача о кратчайшем пути между заданной парой вершин.
Требуется найти кратчайший путь из заданной вершины u в заданную вершину v.

Задача о кратчайшем пути между всеми парами вершин.
Требуется найти кратчайший путь из каждой вершины u в каждую вершину v.

вершин графа до всех остальных
Алгоритм Беллмана — Форда находит кратчайшие

пути от одной вершины графа до всех остальных во взвешенном графе. Вес ребер может быть отрицательным

Алгоритм поиска A* находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе

Алгоритм Флойда — Уоршелла находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа

Находит путь между вершинами s и t графа, содержащий минимальное

количество промежуточных вершин (ребер). Основное применение — трассировки электрических соединений на кристаллах микросхем и на печатных платах.

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

число L(u,v) – длина дуги (расстояния, стоимости и т.п.)
В

общем случае возможно L > 0, L < 0, L = 0.
Под длиной пути понимаем, как и прежде, сумму длин дуг, составляющих путь.
Найти длины кратчайших путей и сами пути от вершины s до всех остальных вершин графа vi.

Известна схема дорог. Требуется перевезти груз из одного пункта в другой по маршруту минимальной длины.
Если в графе нет циклов с отрицательной длиной, то кратчайшие пути существуют и любой кратчайший путь – это простая цепь.

язык Алгол, семафоры, распределенные вычисления)
Лауреат премии Тьюринга (ACM A.M.

Turing Award)
1. Дейкстра Э. Дисциплина программирования = A discipline of programming.
2. Дал У., Дейкстра Э., Хоор К. Структурное программирование = Structured Programming.

Алгоритм основан на приписывании вершинам vi временных меток d(vi). Метка вершины дает верхнюю границу длины пути от s к этой вершине

d(s)=0, считать метку постоянной.
d(vi)=∞, i=1...n, считать метки временными. p=s.

Повторяется n раз, пока не будут упорядочены все вершины.

Шаг 2 (общий шаг).
В дальнейшем на каждом шаге к дереву присоединяется одно новое ребро (и одна вершина). Это ребро выбирается из подходящих ребер, причем подходящим считается ребро, соединяющее вершину дерева с вершиной, ему не принадлежащей. Среди подходящих ребер выбирается ребро наименьшего веса.

Вычисляем метки этих вершин.
d(2) = min (∞; 0 +

7) = 7
d(5) = min (∞; 0 + 9) = 9
d(6) = min (∞; 0 + 2) = 2

(2). Помечаем эту вершину и снова пересчитываем метки вершин, в

которые можно перейти из вершины 6:
d(2) = min (7; 2 + 2) = 4; d(5) = min (9; 2 + 3) = 5;
d(8) = min (∞; 2 + 6) = 8; d(9) = min (9; 2 + 1) = 3

можно перейти из вершины 9. И так далее заполняем остальные

строки таблицы.

в вершине S. Все пути в этом дереве – кратчайшие

для данного графа.

Строится по таблице, в него включаются вершины в том порядке, в котором они получали постоянные метки

мы будем искать кратчайшие маршруты из вершины 1 в вершины

2, 3, 4 и 5.

— источник. Остальным вершинам присвоим метки равные бесконечности.
Рассмотрим все вершины

в которые из вершины 1 есть путь, не содержащий вершин посредников

метки. В данном случае это вершина 2 или 5. Но

из 2 нет ни одного исходящего пути, поэтому мы сразу отмечаем эту вершину как посещенную

Вершина 5 имеет минимальную метку. Рассмотрим все вершины в которые есть прямые пути из 5, но которые ещё не помечены как посещенные

графе, Каждый элемент содержит последнюю промежуточную вершину на кратчайшем пути

между вершиной-источником и конечной вершиной.

В начале алгоритма все элементы вектора Р равны вершине источнику (в нашем случае Р = {1, 1, 1, 1, 1})

В результате получим вектор Р = {1, 1, 5, 5, 1}

Далее на этапе пересчета значения метки для рассматриваемой вершины: если метка рассматриваемой вершины меняется на меньшую, в массив Р мы записываем значение текущей вершины W. Например: у вершины 3 была метка со значением «30», при W=1. Далее при W=5, метка 3-ей вершины изменилась на «20», следовательно мы запишем значение в вектор Р — Р[3]=5

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

достичь.
Шаг 2 (обратный ход). Подставляем значения количества путей: NR = NX + NY + NZ

= 1;
NЖ=NВ+NЕ = 3+1 = 4;
NИ=NД = 4;
NК=NИ+NД+NЖ+NЕ = 4+4+4+1

= 13

аналогично алгоритму Дийкстры.
2. На шаге 2 пересчет величин d(x) производится

для всех вершин, а не только для непомеченных
3. Если для некоторой помеченной вершины происходит уменьшение величины d(x), то с этой вершины и пометка снимается