Кратчайшие пути
Определение кратчайшего пути
В задаче о кратчайшем пути (shortest-paths problem) задается взвешенный ориентированный граф G = (V, Е) с весовой функцией w : Е → R, отображающей ребра на их веса, значения которых выражаются действительными числами.
Вес (weight) пути р = (vo, vi,..., vk) равен суммарному весу входящих в него ребер:
Вес кратчайшего пути (shortest-path weight) из вершины u в вершину v определяется соотношением
Если пути из u в v не существует, то кратчайший путь равен ∞ Тогда по определению кратчайший путь (shortest path) из вершины и в вершину v — это любой путь, вес которого удовлетворяет соотношению w(u,v)=δ(u,v) Вес каждого из ребер можно интерпретировать не как расстояние, а как другую метрику. Часто они используются для представления временных интервалов, стоимости, штрафов, убытков или любой другой величины, которая линейно накапливается по мере продвижения вдоль ребер графа и которую нужно свести к минимуму.
Лемма о частичных путях (подпутях) кратчайшего пути
Лемма (Частичные пути кратчайшего пути являются кратчайшими путями.) Пусть р = (v1, v2..., vk) - кратчайший путь из вершины v1 к вершине vk в заданном взвешенном ориентированном графе G = (V, Е) с весовой функцией w : Е → R, a pij = (vi, vi+i,..., vj) — частичный путь пути р, который проходит из вершины vi к вершине vj для произвольных i и j, удовлетворяющих неравенству 1≤ i ≤ j ≤ k. Тогда pij — кратчайший путь из вершины vi к вершине vj.
Доказательство. Если разложить путь р на составные части
то
будет выполняться соотношение w(p) =
w(p1i) + w(pij) + w(pik).
Теперь предположим, что существует путь рij 1 из вершины Vi к вершине Vj, вес которого удовлетворяет неравенству w (рij 1 )< w(рij )
Тогда
— путь из вершины v1 к вершине vk, вес
которого w(p1i) + w(pij 1 ) + w(pik) меньше веса w
(р). Это противоречит предположению о
том, что р — кратчайший путь из вершины
v1 к вершине vk
Циклы с отрицательным весом
Без потери общности можно предположить, что если ведется поиск кратчайших путей, они не содержат циклов. Поскольку в любой ациклический путь в графе G = (V,E) входит не более |V| различных вершин, в нем также содержится не более |V| — 1 ребер. Таким образом, можно ограничиться рассмотрением кратчайших путей, состоящих не более чем из |V| — 1 ребер.
Пусть G = (V, Е) — взвешенный ориентированный граф с весовой функцией w : Е → R. Предположим, что в нем не содержится циклов с отрицательным весом, достижимых из истока s ∈ V а следовательно, кратчайшие пути вполне определены. Тогда дерево кратчайших путей (shortest-paths tree) с корнем в вершине s — это ориентированный подграф G1 = (V1, Е1'),
в котором множества V1 ⊆ V и Е1⊆ Е определяются такими условиями:
1. V — множество вершин, достижимых из истока s графа G;
2. граф G1 образует корневое дерево с корнем в вершине s;
3. для всех v∈V однозначно определенный простой путь из вершины s в вер- вершину v в графе G1 совпадает с кратчайшим путем из вершины s в вершину v в графе G.
Кратчайшие пути, как и деревья кратчайших путей, не обязательно единственны. Например, на рисунке изображен взвешенный ориентированный граф, на котором обозначен вес каждого из кратчайших путей из истока s а также два дерева кратчайших путей с корнем s
Ослабление ребра
В описанных в этой главе алгоритмах используется метод релаксации, или ослабления (relaxation). Для каждой вершины v∈V поддерживается атрибут d[v], представляющий собой верхнюю границу веса, которым обладает кратчайший путь из истока s в вершину v. Назовем атрибут d[v] оценкой кратчайшего пути (shortest-path estimate). Инициализация оценок кратчайших путей и предшественников производится в приведенной ниже процедуре, время работы которой равно Θ(V):
Initialize_Single_Source(G, s)
1 for (Для) каждой вершины v ∈ V[G]
2 do d[v]←∞
3 π[v] ← NIL 4 d[s]← 0
После инициализации для всех v ∈ V π [v] = NIL, d [s] = 0
и для всех v ∈ V — {s} d [v] = ∞
Процесс релаксации (relaxation) или ослабления ребра (π[v]) заключается в проверке, нельзя ли улучшить найденный до сих пор кратчайший путь к вершине v, проведя его через вершину u, а также в обновлении атрибутов d[v] и π[v] при наличии такой возможности улучшения. Ослабление может уменьшить оценку кратчайшего пути d[v] и обновить поле π[v] вершины v. Приведенный ниже код выполняет ослабление ребра (u,v):
Relax(u, v, w)
1 if d[v] > d[u] + w(u, v)
2 then d[v] ← d[u) + w(u, v)
3 π[v] ← u
Ниже приведены два примера ослабления ребра; в одном из этих примеров оценка кратчайшего пути понижается, а в другом — не происходит никаких изменений, связанных с оценками. В каждой вершине на рисунке приводится оценка кратчайшего пути к этой вершине. В примере, приведенном в части а) рисунка, перед ослаблением выполняется неравенство d[v] > d[u] + w{u,v), поэтому в результате ослабления значение d[v] уменьшается. В части б) рисунка перед ослаблением выполняется неравенство d[v] ≤ d[u] + w(u,v), поэтому значение d[v] остается неизменным.
В каждом из рассмотренных ниже алгоритмов сначала вызывается процедура Initialize_Single__Source, а затем производится ослабление ребер. Более того, ослабление — единственная операция, изменяющая оценки кратчайших путей и предшественников. Описанные ниже алгоритмы различаются тем, сколько раз в них производится ослабление ребер, а также порядком ребер, над которыми выполняется ослабление. В алгоритме Дейкстры и алгоритме поиска кратчайших путей в ориентированных ациклических графах каждое ребро ослабляется ровно по одному разу. В алгоритме Беллмана-Форда (Bellman-Ford) каждое ребро ослабляется по несколько раз. Алгоритм Беллман
Свойства кратчайших путей и ослаблений (стр. 671), особенно свойство ослабления пути
Алгоритм Беллмана-Форда
За время O(|V| × |E|)