🗊Презентация Задача на кратчайший путь

Кратчайшие пути Лекция 5

Задача «Кратчайший путь» Дано: Орграф G, веса c: E(G) → R и две вершины s, t V(G) . Найти s-t-путь минимального веса.

Консервативные веса Определение 5.1 Пусть G ― граф с весами c: E(G) → R . Функция c называется консервативной если не существует цикла отрицательного веса.

Принцип оптимальности Белмана Предложение 5.2 Дан орграф G с консервативными весами c: E(G) → R, и две его вершины s и w. Если e=(v, w) ― последняя дуга некоторого кратчайшего пути P из s в w, тогда P[s,v] (P без ребра e) ― кратчайший путь из s в v.

Доказательство Пусть s-v-путь Q короче пути P[s,v]. Тогда c(Q) + c(e) < c(P). Если wQ, то Q + e короче, чем P. Противоречие  w  Q.

Доказательство (w  Q) Пусть s-v-путь Q короче пути P[s,v]. c(Q) + c(e) < c(P) c(Q[s,w]) = c(Q) + c(e) – c(Q[v,w]+e) < < c(P) – c(Q[v,w]+e) Так как Q[v,w]+e является циклом, то c(Q[s,w]) < c(P) – c(Q[v,w]+e) ≤ c(P). Противоречие.

Замечание Принцип оптимальности Белмана выполняется для всех орграфов с неотрицательными весами и для всех орграфов без циклов. dist(s,s) = 0. dist(s,w) = min{dist(s,v) + c((v,w)): (v,w)  E(G)} для всех w  V(G)/s.

Упражнение 7.1 Дан ациклический орграф G с произвольными весами c: E(G) → R и s, t  V(G). Показать, как найти кратчайший s-t-путь в G за линейное время.

Алгоритм Дейкстры Input: Орграф G, веса c: E(G) → R+ и вершина s V(G). Output: Кратчайшие пути из s во все v  V(G) и их длины. Set l(s)  0. Set l(v)   для всех v V(G)\{s}. Set R  . Найти вершину v  V(G)\R такую, что l(v) = min w V(G)\{R}l(w). Set R  R⋃{v}. For всех w V(G)\R таких, что (v,w)  E(G) do: If l(w) > l(v) + c((v,w)) then l(w)  l(v) + c((v,w)) и p(w)  v. 5) If R ≠ V(G) then go to 2.

Алгоритм Дейкстры (2) Теорема 5.3 (Дейкстра [1959]) Алгоритм Дейкстры находит оптимальное решение за O(n2) элементарных операций (n=|V(G)|).

Скетч доказательства Докажем, что следующие утверждения верны каждый раз когда выполняется шаг 2 алгоритма. a) Для всех v  R и всех w V(G)\R: l(v) ≤ l(w). b) Для всех v  R: l(v) ― длина кратчайшего s-v-пути в G. Если l(v) < , существует s-v- путь длины l(v), последняя дуга которого есть (p(v),v) и все вершины которого принадлежат R. c) Для всех w V(G)\R: l(w) ― длина кратчайшего s-w- пути в G[R⋃{w}]. Если l(w) ≠ , то p(w)  R и l(w) = l(p(w)) + c((p(w), w)).

Алгоритм Дейкстры Input: Орграф G, веса c: E(G) → R+ и вершина s V(G). Output: Кратчайшие пути из s во все v  V(G) и их длины. Set l(s)  0. Set l(v)   для всех v V(G)\{s}. Set R  . Найти вершину v  V(G)\R такую, что l(v) = min w V(G)\{R}l(w). Set R  R⋃{v}. For всех w V(G)\R таких, что (v,w)  E(G) do: If l(w) > l(v) + c((v,w)) then l(w)  l(v) + c((v,w)) и p(w)  v. 5) If R ≠ V(G) then go to 2.

a) Для всех v  R и всех wV(G)\R: l(v) ≤ l(w) Пусть v вершина выбранная на шаге 2. Для любых x  R и y  V(G)\R: l(x) ≤ l(v) ≤ l(y).  a) выполняется после шагов 3 и 4.

b) Для всех v  R: l(v) ― длина кратчайшего s-v-пути в G. Если l(v) < , существует s-v- путь длины l(v), последняя дуга которого есть (p(v),v) и все вершины которого принадлежат R. Так как c) справедливо до шага 3, достаточно показать, что никакой s-v-путь в G, содержащий вершины из V(G)\R не имеет длины короче чем l(v). Пусть  s-v-путь P в G содержащий w  V(G)\R, длина которого меньше l(v). Пусть w будет первая вершина за R на этом пути. c)  l(w) ≤ с(P[s,w]) Так как веса дуг неотрицательны, то с(P[s,w]) ≤ с(P) < l(v).  l(w) < l(v), противоречие с выбором v.

c) Для всех w  V(G)\R: l(w) ― длина кратчайшего s-w- пути в G[R⋃{w}]. Если l(w) ≠ , то p(w)  R и l(w) = l(p(w)) + c((p(w), w)). Пусть после шагов 3 и 4 существует s-w-путь P в G[R⋃w] длины меньше чем l(w) для некоторого wV(G)\R. Тогда P должен содержать v (в противном случае с) нарушалось уже до выполнения шагов 3 и 4). Пусть (x,w)  P. x  R & a)  l(x) ≤ l(v). Шаг 4  l(w) ≤ l(x) + c((x,w)) ≤ l(v) + c((x,w)). b)  l(v) длина кратчайшего s-v-пути. P содержит s-v-путь и (x,w)  l(w) ≤ l(x) + c((x,w)) ≤ c(P). Противоречие.

Алгоритм Дейкстры Теорема 5.3 (Дейкстра [1959]) Алгоритм Дейкстры находит оптимальное решение за O(n2) элементарных операций (n = |V(G)|).

Алгоритм Мура-Беллмана-Форда Input: Орграф G, консервативные веса c: E(G) → R и вершина s V(G). Output: Кратчайшие пути из s во все v  V(G) и их длины. Set l(s)  0 и l(v)   для всех v V(G)\{s}. For i  1 to n – 1 do: For каждой дуги (v,w)  E(G) do If l(w) > l(v) + c((v,w)) then l(w)  l(v) + c((v,w)) и p(w)  v.

Алгоритм Мура-Беллмана-Форда(2) Теорема 5.4 (Moore [1959], Bellman [1958], Ford [1956]) Алгоритм Мура-Беллмана-Форда находит оптимальное решение за O(nm) операций.

Скетч доказательства На каждой итерации алгоритма пусть R  {v V(G): l(v) < } и F  {(x,y)  E(G): x = p(y)}. Тогда a) l(y) ≥ l(x) + c((x,y)) для всех (x,y)  F ; b) Если F содержит цикл C, то C имеет отрицательный суммарный вес; c) Если функция весов c консервативная, то (R, F) ― ордерево с корнем в s.

a) l(y) ≥ l(x) + c((x,y)) для всех (x,y)  F F  {(x,y)  E(G): x = p(y)} Рассмотрим последнюю итерацию, когда p(y) присвоили x. В этот момент l(y) = l(x) + c((x,y)). На последующих итерациях l(y) не менялась, а l(x) могла только уменьшиться.

b) Если F содержит цикл C, то C имеет отрицательный суммарный вес Пусть на некоторой итерации в F образовался цикл C добавлением дуги (x,y). Тогда при проверки в операторе if выполнялось l(y) > l(x) + c((x,y)). a)  l(w) ≥ l(v) + c((v,w)) для всех (v,w)E(С)/{(x,y)}. Cуммируя по всем неравенствам, получаем, что C имеет отрицательный суммарный вес.

c) Если функция весов c консервативная, то (R, F) ― ордерево с корнем в s. b)  F ― ациклический. Для всех xR\{s}: p(x)R  (R,F) ― ордерево с корнем в s. l(x) ― длина s-x-пути в (R,F) для любого x и на всех шагах алгоритма. Докажем, что после k итераций l(x) не превосходит длину кратчайшего s-x-пути среди всех путей, имеющих не больше k дуг.

Индукция Пусть P кратчайший s-x-путь с не более чем k дугами и пусть (w,x) последняя дуга в P. Тогда P[s,w] кратчайший s-w-путь с не более чем k –1 дугой. По индукции l(w) ≤ c(P[s,w]) после k –1 итерации. Проверяя на итерации k дугу (w,x) имеем l(x) ≤ l(w) + c((w,x)) ≤ c(P[). Так как любой путь имеет не более n – 1 дуги, то после n –1 итерации алгоритм находит оптимальное решение.

Алгоритм Мура-Беллмана-Форда Теорема 5.4 (Moore [1959], Bellman [1958], Ford [1956]) Алгоритм Мура-Беллмана-Форда находит оптимальное решение за O(nm) операций. Покажем, что этот алгоритм также может быть использован для проверки есть ли в орграфе циклы отрицательного веса. Попутно определим полезное понятие допустимого потенциала, введенное Эдмондсом и Карпом [1972].

Допустимый потенциал Определение 5.5. Пусть G ― орграф с весами c: E(G) → R, и пусть  : V(G) → R. Тогда для любой (x,y)  E(G) определим пониженную стоимость (x,y) относительно  через c((x,y))  c((x,y)) + (x) – (y). Если c(e) ≥ 0 для всех e  E(G),  называется допустимым потенциалом.

Допустимый потенциал (2) Теорема 5.6 Пусть G ― орграф с весами c: E(G) → R. Допустимый потенциал для (G,c) существует тогда и только тогда, когда функция весов c консервативная.

Доказательство Если  допустимый потенциал, то для каждого цикла C:  веса консервативны. Пусть веса консервативны, добавим новую вершину s и соединим ее со всеми вершинами выходящими дугами нулевого веса. Применим алгоритм Мура-Беллмана-Форда к полученному примеру и найдем величины l(v) для всех v  V(G). l(v) длина кратчайшего s-v-пути для всех v  V(G).  l(w) ≤ l(v) + c((v,w)) для всех (v,w)  E(G). l(v) ― допустимый потенциал.

Допустимый потенциал Следствие 5.7 Дан орграф G с весами c: E(G) → R. Алгоритм Мура-Беллмана-Форда за время O(nm) либо находит допустимый потенциал, либо отрицательный цикл.

Задача «Все Пары Кратчайших путей» Дано: орграф G, веса c: E(G) → R. Найти число lst и вершины pst для всех s, t V(G) с s ≠ t, такие что lst есть длина кратчайшего s-t-пути, и (pst , t) есть последнее ребро такого пути (если оно существует).

Задача «Все Пары Кратчайших путей» (2) Теорема 5.8 Задача «Все Пары Кратчайших путей» может быть решена за время O(n3), где n = |V(G)|.

Алгоритм Флойда-Уоршелла Input: Орграф G с V(G) = {1,...,n} и консервативные веса c: E(G) → R. Output: Матрицы (lij)1≤i,j≤n и (pij)1≤i,j≤n ,где lij ― длина кратчайшего пути из i в j и (pij , j) ― последняя дуга в таком пути (если он существует). Set lij  c((i, j)) для всех (i, j) E(G). Set lij   для всех (i, j) (V(G)× V(G))\ E(G) с i≠j. Set lii  0 для всех i. Set pik  i для всех i, k V(G). For j  1 to n do: For i  1 to n do: If i≠j then: For k  1 to n do: If k≠j then: If lik > lij + ljk then set lik  lij + ljk and pik  pjk

Шаг 2 For j  1 to n do: For i  1 to n do: If i≠j then: For k  1 to n do: If k≠j then: If lik > lij + ljk then set lik  lij + ljk and pik  pjk

Алгоритм Флойда-Уоршелла (2) Теорема 5.9(Floyd [1962], Warshall [1962]) Алгоритм Флойда-Уоршелла находит решение за время O(n3).

Идея доказательства Пусть алгоритм использовал во внешнем цикле (For) вершины j = 1, 2, …, j0. Тогда переменные lik равны длине кратчайшего i-k-пути с внутренними вершинами из множества {1, 2, …, j0} и (pik,k) последняя дуга в таком пути. Утверждение справедливо для j0 = 0 (шаг 1). Справедливость утверждения для j0 = n влечет корректность работы алгоритма.

Индукция: j0 → j0 + 1

Метрическое замыкание Определение 5.10 Дан связный граф G с весами c: E(G) → R+. Метрическим замыканием (G, c) называется пара (Ĝ, ĉ) , где Ĝ ― полный граф на V (G) и ĉ({x,y}) = dist (G, c)(x,y) для всех x, y  V (G).

Метрическое замыкание (2) Следствие 5.11 Пусть G ― связный граф и c: E(G) → R+. Тогда метрическое замыкание (G, c) может быть вычислено за время O(n3).

Задача «Минимальный усредненный Цикл» Дано: орграф G, веса c: E(G) → R. Найти цикл C, усредненный вес которого c(E(C))/|E(C)| минимален, или показать что G ― ациклический.

Как решать? Задача «Минимальный усредненный Цикл» может быть решена динамическим программированием. Можно рассматривать только сильно связные графы. Достаточно существования одной вершины из которой достижимы другие.

Теорема Карпа Теорема 5.12 (Karp [1978]) Пусть G ― орграф с весами c: E(G) → R. Пусть s V(G) так, что каждая вершина достижима из s. Для x V(G) и k  Z+ Пусть будет последовательность дуг минимального веса из s в x длины k (и ∞, если не существует). Пусть μ(G) ― значение минимального усредненного цикла в G. Тогда

Идея доказательства Докажем, что если μ(G) = 0 то Пусть G ― орграф с μ(G) = 0. В G нет отрицательных циклов. Для x  V(G), пусть l(x) длина кратчайшего s-x-пути. Так как c ― консервативны, то

Доказательство Покажем, что существует такое x, что Fn(x) = l(x). μ(G) = 0  существует цикл C нулевого веса. Пусть w  C и P кратчайший s-w-путь.

Алгоритм «Минимальный усредненный Цикл» Input: Орграф G, веса c: E(G) → R. Output: Цикл C с минимальным усредненным весом или информация, что G ― ациклический. Добавим вершину s и ребро (s,x) с c((s,x))=0 для всех x  V(G). Set n:=|V(G)|, F0(s):=0 и F0(x):=∞ для всех x  V(G)\{s}. For k := 1 to n do: For всех x  V(G) do: Fk(x):=∞. For всех (w, x)  δ−(x) do: If Fk−1(w)+ c((w,x)) < Fk(x) then: Set Fk(x) := Fk−1(w)+ c((w,x)) и pk(x):=w. If Fn(x)=∞ для всех x  V(G) then stop (G ― ациклический). Пусть x ― вершина: минимален. 6. Пусть C ― любой цикл, заданный ребрами pn(x), pn−1 (pn(x)),…

Алгоритм «Минимальный усредненный Цикл» Следствие 5.13(Karp [1978]) Алгоритм «Минимальный усредненный Цикл» находит решение за время O(n(m+n)).

Упражнение 7.2 Дан орграф G с произвольными весами c: E(G) → R и s, t  V(G). Найти s-t-путь у которого вес максимального ребра минимален.

Упражнение 7.3 Дан орграф G с s, t  V(G). Пусть для каждого ребра e E(G) задано число r(e) (надежность ребра e), 0 ≤ r(e) ≤ 1. Надежность пути P определяется произведением надежности его ребер. Найти s-t-путь максимальной надежности.

Упражнение 7.4 Пусть G ― орграф с консервативными весами c: E(G) → R . Пусть s, t  V(G), так что t достижимо из s. Доказать, что минимум длины s-t-пути в G равен максимуму величины π(t) − π(s), где π ― допустимый потенциал.

Упражнение 7.5 Пусть G полный граф и c: E(G) → R+. Показать, что (G,c) является собственным метрическим замыканием тогда и только тогда, когда выполняется неравенство треугольника: c({x,y}) + c({y,z}) ≥ c({x,z}) для любых трех вершин x, y, z  V(G).