Кратчайшие пути Лекция 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). Противоречие. s v w Q 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) и их длины. 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.

Алгоритм Дейкстры (2) Теорема 5.3 (Дейкстра [1959]) Алгоритм Дейкстры находит оптимальное решение за O(n 2 ) элементарных операций (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)

Алгоритм Дейкстры 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.

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)

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(n 2 ) элементарных операций (n = |V(G)|).

Алгоритм Мура-Беллмана-Форда 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.

Алгоритм Мура-Беллмана-Форда(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 имеет отрицательный суммарный вес. x y v w

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. Найти число l st и вершины p st для всех s, t V(G) с s t, такие что l st есть длина кратчайшего s-t-пути, и (p st, t) есть последнее ребро такого пути (если оно существует).

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

Алгоритм Флойда-Уоршелла 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

Шаг 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

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

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

Индукция: 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

Метрическое замыкание Определение 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(n 3 ).

Задача «Минимальный усредненный Цикл» Дано: орграф 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, что F n (x) = l(x). μ(G) = 0 существует цикл C нулевого веса. Пусть w C и P кратчайший s-w-путь. P С n раз w x s

Алгоритм «Минимальный усредненный Цикл» 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)),…

Алгоритм «Минимальный усредненный Цикл» Следствие 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).