Лекция 7. Задача о кратчайшем пути в ориентированном графе. Алгоритм Форда-Беллмана. Алгоритм Дейкстры (Лекции 2016 года)

Методы дискретной оптимизацииЗадача о кратчайшем пути вориентированном графе. АлгоритмФорда-Беллмана. Алгоритм Дейкстры.1 / 12Основные понятия. Постановка задачиОпределение.Взвешенный орграф Ḡ = (V, E, c) называется сетью. Ориентированныймаршрут называется путем.Определение.Пусть P – некоторый (v, w)-путь:v = v0 → v1 → . . .

→ vk = wТогда l(P ) = c(e1 ) + c(e2 ) + · · · + c(ek ) называется длиной пути P , где ei –ребро перехода от вершины vi−1 к вершине vi .(u, w)-путь с наименьшей длиной называется кратчайшим.Задача о кратчайшем пути (ЗКП)Задача о кратчайшем пути между фиксированными вершинами: взаданной сети Ḡ с двумя выделенными вершинами s и t найтикратчайший (s, t)-путь.2 / 12Общий случай. Алгоритм Форда-БеллманаОбщие замечания: Будем предполагать, что если вершины v и w неявляются смежными в Ḡ, то c(v, w) = ∞. Также будем считать, чторассматриваемая сеть не содержит контуров отрицательной длины.Схема вычисления:1.

Размечаются все вершины сети и вычисляются длины кратчайшихпутей от s до всех вершин.2. Используя специальные метки, обратным ходом строится кратчайшийпуть.Замечание. Для вычисления длины кратчайшего пути от s до tнеобходимо вычислить длины кратчайших путей от s до всех вершин.3 / 12Алгоритм Форда-БеллманаЛестер Форд (1956), Ричард Беллман (1958).Основная идея: поэтапное вычисление кратчайших расстояний.Обозначим через dk (v) длину кратчайшего среди всех (s, v)-путей,содержащих не более k ребер. Тогдаd1 (v) ≥ d2 (v) ≥ · · · ≥ dn−1 (v).В графе нет контуров отрицательной длины, следовательно, кратчайший(s, v)-путь не может содержать более n − 1 ребра и dn−1 (v) – длинакратчайшего пути из s в v.Для вычисления dn−1 (v) достаточно последовательно вычислять dk (v) длявсех k = 1, ..., n − 1:d1 (v) = c(s, v), ∀v ∈ Vdk+1 (v) = min{dk (v), dk (w) + c(w, v)|w ∈ V }4 / 12Алгоритм Форда-БеллманаОписанные вычисления возможно организовать с помощью одномерногомассива D длины n.

Положив D[v] = c(s, v), ∀v ∈ V , получимD[v] = d1 (v).Просматривая далее все вершины v, пересчитаем значения D[v]следующим образом:D[v] = min{D[v], D[w] + c(w, v)|w ∈ V }.После первого пересчета значений D[v] для всех v, получим, чтоD[v] ≤ d2 (v). Повторив n − 2 раза пересчет D[v], будем иметь равенстваD[v] = dn−1 (v), ∀v ∈ VПостроение кратчайших путей будем вести с помощью одномерногомассива P revious длины n, где P revious[v] дает имя вершины,предпоследней в кратчайшем (s, v)-пути.5 / 12Алгоритм Форда-БеллманаФормальное описание алгоритмаВХОД: Ḡ = (V, E, c) – сеть, A – матрица весов порядка n, вершины s и t.ВЫХОД: D[v] – кратчайшие расстояния от s до всех v ∈ V , S –кратчайший (s, t)-путь или сообщение, что искомого пути не существует.1.

procedure Distance2. begin3. D[s] = 0; P revious[s] := 0;4. for v ∈ V \{s} do5.begin D[v] := A[s, v]; P revious[v] := s end6. for k := 1 to n − 2 do7.for v ∈ V \{s} do8.for w ∈ V do9.if D[w] + A[w, v] < D[v] then10.begin11.D[v] := D[w] + A[w, v];12.P revious[v] := w13.end14. end6 / 12Алгоритм Форда-Беллмана15. begin16.Distance17.if D[t] < ∞ then18.begin19.S := nil; S ⇐ t; v := t;20.while P revious[v] 6= 0 dobegin v := P revious[v]; S ⇐ v end21.22.23.endelse writeln("Not exists");24.

endСложность алгоритма Форда-Беллмана: O(n3 ) = O((n − 2) · (n − 1) · n).7 / 12Пример8 / 12Алгоритм ДейкстрыЭдсгер Дейкстра (1959)Алгоритм Дейкстры позволяет вычислять в сети с неотрицательнымивесами кратчайшие расстояния от фиксированной вершины s до всехостальных вершин и находить кратчайшие пути более эффективно, чемалгоритм Форда-Беллмана. В основе алгоритма Дейкстры лежит принцип«жадности», заключающийся в последовательном вычислениикратчайших расстояний сначала до ближайшей к s вершине, затем доследующей ближайшей и т.

д.Обозначим через d(v) расстояние от s до v, т. е. длину кратчайшего(s, v)-пути в сети Ḡ.Первая ближайшая к вершине s вершина v это сама вершина s и d(s) = 0.Пусть ближайшие k вершин к вершине s определены и для всех нихвычислены кратчайшие расстояния d(v), т.е. определено множествоS = {v1 = s, v2 , ..., vk }, причем выполняются неравенства:1)0 = d(v1 ) ≤ d(v2 ) ≤ ...

≤ d(vk )2)d(vk ) ≤ d(v), ∀v ∈ V \S9 / 12Алгоритм ДейкстрыНайдем следующую ближайшую к s вершину сети Ḡ. Для каждогоw ∈ V \S положимD(w) = min{d(v) + c(v, w)|v ∈ S}D(w) определяет длину минимального (s, w)-пути среди всех (s, w)-путей,все вершины в котором, кроме w, принадлежатS.Выберем такую вершину w∗ ∈ V \S что выполнено условие:D(w∗ ) = min{D(w)|w ∈ V \S}.Вершина w∗ является самой близкой к s среди всех вершин, не входящихв S (она является следующей (k + 1)-й ближайшей к s вершиной), икратчайшее расстояние от вершины s до вершины w∗ в точности равноD(w∗ ) т.е. d(w∗ ) = D(w∗ ).Таким образом, выбирая вершину w ∈ V \S с минимальным значениемD[v] и добавляя к S, мы расширяем множество вершин, до которыхвычислено расстояние, на один элемент.

Повторяя процесс расширенияn − 1 раз, мы вычислим расстояние до всех вершин Ḡ10 / 12Алгоритм ДейкстрыФормальное описание алгоритмаВХОД: Ḡ = (V, E, c) – сеть, A – матрица весов порядка n, вершина s.ВЫХОД: D[v] – кратчайшие расстояния от s до всех v ∈ V , P revious[v] –предпоследняя вершина в кратчайшем (s, v)-пути.1.

begin2. D[s] = 0; P revious[s] := 0; F := V \{s}3. for v ∈ F do4.begin D[v] := A[s, v]; P revious[v] := s end5. for k := 1 to n − 1 do6.begin7.w := M in(F ); F := F \{w} // M in(F ) = Arg minw∈F D(w)8.for v ∈ F do9.if D[w] + A[w, v] < D[v] then10.begin11.D[v] := D[w] + A[w, v];12.P revious[v] := w13.end14.end15. end11 / 12Алгоритм Дейкстры. ПримерСложность алгоритма Дейкстры:O(n + (n − 1) + ... + 1) = O(n(n − 1)/2) = O(n2 ).Пример12 / 12.