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

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

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

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

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

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

6 Доказательство (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). Противоречие. s v w Q P

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

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

9 Алгоритм Дейкстры Input: Орграф G, веса c: E(G) R + и вершина s V(G). Output: Кратчайшие пути из s во все v V(G) и их длины. 1) Set l(s) 0. Set l(v) для всех v V(G)\{s}. Set R. 2) Найти вершину v V(G)\R такую, что l(v) = min w V(G)\{R} l(w). 3) Set R R {v}. 4) 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.

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

11 Скетч доказательства Докажем, что следующие утверждения верны каждый раз когда выполняется шаг 2 алгоритма. a) Для всех v R и всех w V(G)\R: l(v) l(w). b) Для всех v R: l(v) длина кратчайшего s-v- пути в G. Если l(v)

12 Алгоритм Дейкстры Input: Орграф G, веса c: E(G) R + и вершина s V(G). Output: Кратчайшие пути из s во все v V(G) и их длины. 1) Set l(s) 0. Set l(v) для всех v V(G)\{s}. Set R. 2) Найти вершину v V(G)\R такую, что l(v) = min w V(G)\{R} l(w). 3) Set R R {v}. 4) 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.

13 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.

14 b) Для всех v R: l(v) длина кратчайшего s-v-пути в G. Если l(v)

15 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). Противоречие.

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

17 Алгоритм Мура-Беллмана-Форда Input: Орграф G, консервативные веса c: E(G) R и вершина s V(G). Output: Кратчайшие пути из s во все v V(G) и их длины. 1) Set l(s) 0 и l(v) для всех v V(G)\{s}. 2) 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.

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

19 Скетч доказательства На каждой итерации алгоритма пусть 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.

20 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) могла только уменьшиться.

21 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 имеет отрицательный суммарный вес. x y v w

22 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 дуг.

23 Индукция Пусть 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 итерации алгоритм находит оптимальное решение.

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

25 Допустимый потенциал Определение 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), называется допустимым потенциалом.

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

27 Доказательство Если допустимый потенциал, то для каждого цикла 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) допустимый потенциал.

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

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

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

31 Алгоритм Флойда-Уоршелла Input: Орграф G с V(G) = {1,...,n} и консервативные веса c: E(G) R. Output: Матрицы (l ij ) 1i,jn и (p ij ) 1i,jn,где l ij длина кратчайшего пути из i в j и (p ij, j) последняя дуга в таком пути (если он существует). 1)Set l ij c((i, j)) для всех (i, j) E(G). Set l ij для всех (i, j) (V(G)× V(G))\ E(G) с ij. Set l ii 0 для всех i. Set p ik i для всех i, k V(G). 2)For j 1 to n do: For i 1 to n do: If ij then: For k 1 to n do: If kj then: If l ik > l ij + l jk then set l ik l ij + l jk and p ik p jk

32 Шаг 2 For j 1 to n do: For i 1 to n do: If ij then: For k 1 to n do: If kj then: If l ik > l ij + l jk then set l ik l ij + l jk and p ik p jk j i k p jk

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

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

35 Индукция: j 0 j j=j 0 +1 i k {1, 2, …, j 0 } Для любых i и k при выполнения шага 2 для j = j 0 + 1: l ik заменяется на l ij + l jk, если l ik > l ij + l jk. Пусть l ik получило новое значение. Осталось показать, что в этом случае i-(j 0 + 1)-путь P и (j 0 + 1)-k-путь Q не имеют общих внутренних вершин. Q P

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

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

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

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

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

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

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

43 Алгоритм «Минимальный усредненный Цикл» Input: Орграф G, веса c: E(G) R. Output: Цикл C с минимальным усредненным весом или информация, что G ациклический. 1. Добавим вершину s и ребро (s,x) с c((s,x))=0 для всех x V(G). 2.Set n:=|V(G)|, F 0 (s):=0 и F 0 (x):= для всех x V(G)\{s}. 3.For k := 1 to n do: For всех x V(G) do: F k (x):=. For всех (w, x) δ (x) do: If F k1 (w)+ c((w,x)) < F k (x) then: Set F k (x) := F k1 (w)+ c((w,x)) и p k (x):=w. 4.If F n (x)= для всех x V(G) then stop (G ациклический ). 5.Пусть x вершина: минимален. 6. Пусть C любой цикл, заданный ребрами p n (x), p n1 (p n (x)),…

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

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

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

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

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