Кратчайшие пути

Содержание

1. Кратчайшие пути
2. Задача «Кратчайший путь»Дано: Орграф G, веса c:
3. Консервативные весаОпределение 5.1 Пусть G ― граф
4. Принцип оптимальности Белмана Предложение 5.2
5. ДоказательствоПусть s-v-путь Q короче пути P[s,v].Тогда c(Q)
6. Доказательство (w  Q)Пусть s-v-путь Q короче
7. ЗамечаниеПринцип оптимальности Белмана выполняется для всех орграфов
8. Упражнение 7.1Дан ациклический орграф G с произвольными
9. Алгоритм ДейкстрыInput: Орграф G, веса c: E(G)
10. Алгоритм Дейкстры (2)Теорема 5.3 (Дейкстра [1959])
11. Скетч доказательства Докажем, что следующие утверждения
12. Алгоритм ДейкстрыInput: Орграф G, веса c: E(G)
13. a) Для всех v  R и
14. b) Для всех v  R:
15. c) Для всех w  V(G)\R: l(w)
16. Алгоритм Дейкстры Теорема 5.3 (Дейкстра [1959])
17. Алгоритм Мура-Беллмана-Форда Input: Орграф G, консервативные веса
18. Алгоритм Мура-Беллмана-Форда(2)Теорема 5.4 (Moore [1959], Bellman [1958],
19. Скетч доказательстваНа каждой итерации алгоритма пусть
20. a) l(y) ≥ l(x) + c((x,y)) для
21. b) Если F содержит цикл C, то
22. c) Если функция весов c консервативная, то
23. ИндукцияПусть P кратчайший s-x-путь с не более
24. Алгоритм Мура-Беллмана-ФордаТеорема 5.4 (Moore [1959], Bellman [1958],
25. Допустимый потенциалОпределение 5.5. Пусть G ― орграф
26. Допустимый потенциал (2)Теорема 5.6 Пусть
27. ДоказательствоЕсли  допустимый потенциал, то для каждого
28. Допустимый потенциал Следствие 5.7 Дан
29. Задача «Все Пары Кратчайших путей»Дано: орграф G,
30. Задача «Все Пары Кратчайших путей» (2)Теорема 5.8
31. Алгоритм Флойда-Уоршелла Input: Орграф G с V(G)
32. Шаг 2 For j 
33. Алгоритм Флойда-Уоршелла (2)Теорема 5.9(Floyd [1962], Warshall [1962]) Алгоритм Флойда-Уоршелла находит решение за время O(n3).
34. Идея доказательстваПусть алгоритм использовал во внешнем цикле
35. Индукция: j0 → j0 + 1j=j0+1ik{1, 2,
36. Метрическое замыканиеОпределение 5.10 Дан связный граф G
37. Метрическое замыкание (2)Следствие 5.11 Пусть G
38. Задача «Минимальный усредненный Цикл»Дано: орграф G, веса
39. Как решать?Задача «Минимальный усредненный Цикл» может быть
40. Теорема КарпаТеорема 5.12 (Karp [1978])Пусть G ―
41. Идея доказательстваДокажем, что если μ(G) = 0
42. ДоказательствоПокажем, что существует такое x, что Fn(x)
43. Алгоритм «Минимальный усредненный Цикл»Input: Орграф G, веса
44. Алгоритм «Минимальный усредненный Цикл» Следствие 5.13(Karp
45. Упражнение 7.2Дан орграф G с произвольными весами
46. Упражнение 7.3Дан орграф G с s, t
47. Упражнение 7.4Пусть G ― орграф с консервативными
48. Упражнение 7.5Пусть G полный граф и c:
49. Скачать презентанцию

Задача «Кратчайший путь»Дано: Орграф 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-путь минимального веса.

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

Слайд 3Консервативные веса
Определение 5.1 Пусть G ― граф с весами c:

E(G) → R . Функция c называется консервативной если

не существует цикла отрицательного веса.

Консервативные весаОпределение 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.2 Дан орграф G с консервативными весами c: E(G) →

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

c(P).
Если wQ, то Q + e короче, чем P.
Противоречие 

w  Q.

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

Слайд 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).
Противоречие.

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

Слайд 7Замечание
Принцип оптимальности Белмана выполняется для всех орграфов с неотрицательными весами

и для всех орграфов без циклов.

dist(s,s) = 0.
dist(s,w) = min{dist(s,v)

+ c((v,w)): (v,w)  E(G)}
для всех w  V(G)/s.

ЗамечаниеПринцип оптимальности Белмана выполняется для всех орграфов с неотрицательными весами и для всех орграфов без циклов.dist(s,s) =

Слайд 8Упражнение 7.1
Дан ациклический орграф G с произвольными весами c: E(G)

→ R и s, t  V(G).
Показать, как

найти кратчайший s-t-путь в G за линейное время.

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

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

Алгоритм ДейкстрыInput: Орграф G, веса c: E(G) → R+ и вершина s V(G). Output: Кратчайшие пути из

Слайд 10Алгоритм Дейкстры (2)
Теорема 5.3 (Дейкстра [1959])
Алгоритм Дейкстры находит

оптимальное решение за O(n2) элементарных операций (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) < , существует 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)).

Скетч доказательства Докажем, что следующие утверждения верны каждый раз когда выполняется шаг 2 алгоритма. a) Для

Слайд 12Алгоритм Дейкстры
Input: Орграф G, веса c: E(G) → R+ и

вершина s V(G).
Output: Кратчайшие пути из s во все

Слайд 13a) Для всех 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.

$a) Для всех v  R и всех wV(G)\R: l(v) ≤ l(w)Пусть v вершина выбранная на шаге$

Слайд 14 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.

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

Слайд 15c) Для всех 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).
Противоречие.

$c) Для всех w  V(G)\R: l(w) ― длина кратчайшего$

Слайд 16Алгоритм Дейкстры
Теорема 5.3 (Дейкстра [1959])
Алгоритм Дейкстры находит

оптимальное решение за O(n2) элементарных операций (n = |V(G)|).

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

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

Алгоритм Мура-Беллмана-Форда Input: Орграф G, консервативные веса c: E(G) → R и вершина s V(G). Output: Кратчайшие

Слайд 18Алгоритм Мура-Беллмана-Форда(2)
Теорема 5.4 (Moore [1959], Bellman [1958], Ford [1956])
Алгоритм

Мура-Беллмана-Форда находит оптимальное решение за O(nm) операций.

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

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

a) l(y) ≥ l(x) + c((x,y)) для всех (x,y)  FF  {(x,y)  E(G): x =

Слайд 21b) Если 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 имеет отрицательный суммарный вес.

b) Если F содержит цикл C, то C имеет отрицательный суммарный весПусть на некоторой итерации в F

Слайд 22c) Если функция весов 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 дуг.

c) Если функция весов c консервативная, то (R, F) ― ордерево с корнем в s.b)  F

Слайд 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 итерации алгоритм находит оптимальное решение.

ИндукцияПусть P кратчайший s-x-путь с не более чем k дугами и пусть (w,x) последняя дуга в P.Тогда

Слайд 24Алгоритм Мура-Беллмана-Форда
Теорема 5.4 (Moore [1959], Bellman [1958], Ford [1956])

Алгоритм Мура-Беллмана-Форда находит оптимальное решение за O(nm) операций.

Покажем, что этот

алгоритм также может быть использован для проверки есть ли в орграфе циклы отрицательного веса.
Попутно определим полезное понятие допустимого потенциала, введенное Эдмондсом и Карпом [1972].

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

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

Допустимый потенциалОпределение 5.5. Пусть G ― орграф с весами c: E(G) → R, и пусть  :

Слайд 26Допустимый потенциал (2)
Теорема 5.6
Пусть G ― орграф

с весами c: E(G) → R. Допустимый потенциал для (G,c)

существует тогда и только тогда, когда функция весов c консервативная.

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

Слайд 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) ― допустимый потенциал.

ДоказательствоЕсли  допустимый потенциал, то для каждого цикла C: веса консервативны.Пусть веса консервативны, добавим новую вершину s

Слайд 28Допустимый потенциал
Следствие 5.7
Дан орграф G с

весами c: E(G) → R. Алгоритм Мура-Беллмана-Форда за время O(nm)

либо находит допустимый потенциал, либо отрицательный цикл.

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

Слайд 29Задача «Все Пары Кратчайших путей»
Дано: орграф G, веса c: E(G)

→ R.
Найти число lst и вершины pst для всех s,

t V(G) с s ≠ t, такие что lst есть длина кратчайшего s-t-пути, и (pst , t) есть последнее ребро такого пути (если оно существует).

Задача «Все Пары Кратчайших путей»Дано: орграф G, веса c: E(G) → R.Найти число lst и вершины pst

Слайд 30Задача «Все Пары Кратчайших путей» (2)

Теорема 5.8
Задача «Все Пары

Кратчайших путей» может быть решена за время O(n3), где n

= |V(G)|.

Задача «Все Пары Кратчайших путей» (2)Теорема 5.8 Задача «Все Пары Кратчайших путей» может быть решена за время

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

Алгоритм Флойда-Уоршелла Input: Орграф G с V(G) = {1,...,n} и консервативные веса c: E(G) →

Слайд 32Шаг 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

pjk

Слайд 33Алгоритм Флойда-Уоршелла (2)

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

решение за время O(n3).

Слайд 34Идея доказательства
Пусть алгоритм использовал во внешнем цикле (For) вершины j

= 1, 2, …, j0. Тогда переменные lik равны длине

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

Идея доказательстваПусть алгоритм использовал во внешнем цикле (For) вершины j = 1, 2, …, j0. Тогда переменные

Слайд 35Индукция: j0 → j0 + 1
j=j0+1
i
k
{1, 2, …, j0}
Для любых

i и k при выполнения шага 2
для j =

j0 + 1: lik заменяется на lij + ljk ,
если lik > lij + ljk .

Пусть lik получило новое значение.
Осталось показать, что в этом
случае i-(j0 + 1)-путь P и (j0 + 1)-k-путь Q
не имеют общих внутренних вершин.

Индукция: j0 → j0 + 1j=j0+1ik{1, 2, …, j0}Для любых i и k при выполнения шага 2

Слайд 36Метрическое замыкание
Определение 5.10
Дан связный граф G с весами

c: E(G) → R+.
Метрическим замыканием (G, c) называется пара

(Ĝ, ĉ) , где Ĝ ― полный граф на V (G) и ĉ({x,y}) = dist (G, c)(x,y) для всех x, y  V (G).

Метрическое замыканиеОпределение 5.10 Дан связный граф G с весами c: E(G) → R+. Метрическим замыканием (G, c)

Слайд 37Метрическое замыкание (2)
Следствие 5.11
Пусть G ― связный

граф и c: E(G) → R+. Тогда метрическое замыкание (G,

c) может быть вычислено за время O(n3).

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

Слайд 38Задача «Минимальный усредненный Цикл»

Дано: орграф G, веса c: E(G) →

R.
Найти цикл C, усредненный вес которого c(E(C))/|E(C)| минимален, или показать

что G ― ациклический.

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

Слайд 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. Тогда

Теорема КарпаТеорема 5.12 (Karp [1978])Пусть G ― орграф с весами c: E(G) → R. Пусть s V(G)

Слайд 41Идея доказательства
Докажем, что если μ(G) = 0 то

Пусть G ―

орграф с μ(G) = 0. В G нет отрицательных циклов.

Для x  V(G), пусть l(x) длина кратчайшего s-x-пути. Так как c ― консервативны, то

Идея доказательстваДокажем, что если μ(G) = 0 тоПусть G ― орграф с μ(G) = 0. В G

Слайд 42Доказательство
Покажем, что существует такое x, что Fn(x) = l(x).
μ(G) =

0  существует цикл C нулевого веса.
Пусть w  C

и P кратчайший s-w-путь.

n раз

ДоказательствоПокажем, что существует такое x, что Fn(x) = l(x).μ(G) = 0  существует цикл C нулевого веса.Пусть

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

Алгоритм «Минимальный усредненный Цикл»Input: Орграф G, веса c: E(G) → R. Output: Цикл C с минимальным усредненным

Слайд 44Алгоритм «Минимальный усредненный Цикл»
Следствие 5.13(Karp [1978])
Алгоритм

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

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

Слайд 45Упражнение 7.2
Дан орграф G с произвольными весами

c: E(G) → R и s, t  V(G).

Найти s-t-путь у которого вес максимального ребра минимален.

Упражнение 7.2Дан орграф G с произвольными весами c: E(G) → R и s,

Слайд 46Упражнение 7.3
Дан орграф G с s, t  V(G). Пусть

для каждого ребра e E(G) задано число r(e)

(надежность ребра e), 0 ≤ r(e) ≤ 1. Надежность пути P определяется произведением надежности его ребер.
Найти s-t-путь максимальной надежности.

Упражнение 7.3Дан орграф G с s, t  V(G). Пусть для каждого ребра e E(G) задано число

Слайд 47Упражнение 7.4
Пусть G ― орграф с консервативными весами c: E(G)

→ R . Пусть s, t  V(G), так что

t достижимо из s.
Доказать, что минимум длины s-t-пути в G равен максимуму величины π(t) − π(s), где π ― допустимый потенциал.

Упражнение 7.4Пусть G ― орграф с консервативными весами c: E(G) → R . Пусть s, t 

Слайд 48Упражнение 7.5
Пусть G полный граф и c: E(G) → R+.

Показать, что (G,c) является собственным метрическим замыканием тогда и только

тогда, когда выполняется неравенство треугольника: c({x,y}) + c({y,z}) ≥ c({x,z}) для любых трех вершин x, y, z  V(G).

Упражнение 7.5Пусть G полный граф и c: E(G) → R+. Показать, что (G,c) является собственным метрическим замыканием

Скачать презентацию

Разделы презентаций

Кратчайшие пути

Содержание

Слайды и текст этой презентации

Слайд 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, и две

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

c(P).Если wQ, то Q + e короче, чем P.Противоречие 

Слайд 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)

Слайд 7ЗамечаниеПринцип оптимальности Белмана выполняется для всех орграфов с неотрицательными весами

и для всех орграфов без циклов.dist(s,s) = 0.dist(s,w) = min{dist(s,v)

Слайд 8Упражнение 7.1Дан ациклический орграф G с произвольными весами c: E(G)

→ R и s, t  V(G). Показать, как

Слайд 9Алгоритм ДейкстрыInput: Орграф G, веса c: E(G) → R+ и

вершина s V(G). Output: Кратчайшие пути из s во все

Слайд 10Алгоритм Дейкстры (2)Теорема 5.3 (Дейкстра [1959]) Алгоритм Дейкстры находит

оптимальное решение за O(n2) элементарных операций (n=|V(G)|).

Слайд 11Скетч доказательства Докажем, что следующие утверждения верны каждый раз

когда выполняется шаг 2 алгоритма. a) Для всех v 

Слайд 12Алгоритм ДейкстрыInput: Орграф G, веса c: E(G) → R+ и

вершина s V(G). Output: Кратчайшие пути из s во все

Слайд 13a) Для всех v  R и всех wV(G)\R: l(v)

≤ l(w)Пусть v вершина выбранная на шаге 2.Для любых x

Слайд 14 b) Для всех v  R: l(v) ― длина

кратчайшего s-v-пути в G. Если l(v) < , существует s-v-

Слайд 15c) Для всех w  V(G)\R: l(w) ― длина кратчайшего

Слайд 16Алгоритм Дейкстры Теорема 5.3 (Дейкстра [1959]) Алгоритм Дейкстры находит

оптимальное решение за O(n2) элементарных операций (n = |V(G)|).

Слайд 17Алгоритм Мура-Беллмана-Форда Input: Орграф G, консервативные веса c: E(G) →

R и вершина s V(G). Output: Кратчайшие пути из s

Слайд 18Алгоритм Мура-Беллмана-Форда(2)Теорема 5.4 (Moore [1959], Bellman [1958], Ford [1956]) Алгоритм

Мура-Беллмана-Форда находит оптимальное решение за O(nm) операций.

Слайд 19Скетч доказательстваНа каждой итерации алгоритма пусть

Слайд 20a) l(y) ≥ l(x) + c((x,y)) для всех (x,y) 

FF  {(x,y)  E(G): x = p(y)}Рассмотрим последнюю итерацию,

Слайд 21b) Если F содержит цикл C, то C имеет отрицательный

суммарный весПусть на некоторой итерации в F образовался цикл C

Слайд 22c) Если функция весов c консервативная, то (R, F) ―

ордерево с корнем в s.b)  F ― ациклический.Для всех

Слайд 23ИндукцияПусть P кратчайший s-x-путь с не более чем k дугами

и пусть (w,x) последняя дуга в P.Тогда P[s,w] кратчайший s-w-путь

Слайд 24Алгоритм Мура-Беллмана-ФордаТеорема 5.4 (Moore [1959], Bellman [1958], Ford [1956])

Алгоритм Мура-Беллмана-Форда находит оптимальное решение за O(nm) операций.Покажем, что этот

Слайд 25Допустимый потенциалОпределение 5.5. Пусть G ― орграф с весами c:

E(G) → R, и пусть  : V(G) → R.

Слайд 26Допустимый потенциал (2)Теорема 5.6 Пусть G ― орграф

с весами c: E(G) → R. Допустимый потенциал для (G,c)

Слайд 27ДоказательствоЕсли  допустимый потенциал, то для каждого цикла C: веса

консервативны.Пусть веса консервативны, добавим новую вершину s и соединим ее

Слайд 28Допустимый потенциал Следствие 5.7 Дан орграф G с

весами c: E(G) → R. Алгоритм Мура-Беллмана-Форда за время O(nm)

Слайд 29Задача «Все Пары Кратчайших путей»Дано: орграф G, веса c: E(G)

→ R.Найти число lst и вершины pst для всех s,

Слайд 30Задача «Все Пары Кратчайших путей» (2)Теорема 5.8 Задача «Все Пары

Кратчайших путей» может быть решена за время O(n3), где n

Слайд 31Алгоритм Флойда-Уоршелла Input: Орграф G с V(G) = {1,...,n} и

консервативные веса c: E(G) → R.Output: Матрицы (lij)1≤i,j≤n

Слайд 32Шаг 2 For j  1 to n

do: For i 

Слайд 33Алгоритм Флойда-Уоршелла (2)Теорема 5.9(Floyd [1962], Warshall [1962]) Алгоритм Флойда-Уоршелла находит

решение за время O(n3).

Слайд 34Идея доказательстваПусть алгоритм использовал во внешнем цикле (For) вершины j

= 1, 2, …, j0. Тогда переменные lik равны длине

Слайд 35Индукция: j0 → j0 + 1j=j0+1ik{1, 2, …, j0}Для любых

i и k при выполнения шага 2 для j =

Слайд 36Метрическое замыканиеОпределение 5.10 Дан связный граф G с весами

c: E(G) → R+. Метрическим замыканием (G, c) называется пара

Слайд 37Метрическое замыкание (2)Следствие 5.11 Пусть G ― связный

граф и c: E(G) → R+. Тогда метрическое замыкание (G,

Слайд 38Задача «Минимальный усредненный Цикл»Дано: орграф G, веса c: E(G) →

R.Найти цикл C, усредненный вес которого c(E(C))/|E(C)| минимален, или показать

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

рассматривать только сильно связные графы.Достаточно существования одной вершины из которой

Слайд 40Теорема КарпаТеорема 5.12 (Karp [1978])Пусть G ― орграф с весами

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

Слайд 2Задача «Кратчайший путь»
Дано: Орграф G, веса c: E(G) → R

и две вершины s, t V(G) .
Найти s-t-путь минимального веса.

Слайд 3Консервативные веса
Определение 5.1 Пусть G ― граф с весами c:

Слайд 4Принцип оптимальности Белмана
Предложение 5.2
Дан орграф

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

c(P).
Если wQ, то Q + e короче, чем P.
Противоречие 

Слайд 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)

Слайд 7Замечание
Принцип оптимальности Белмана выполняется для всех орграфов с неотрицательными весами

и для всех орграфов без циклов.

dist(s,s) = 0.
dist(s,w) = min{dist(s,v)

Слайд 8Упражнение 7.1
Дан ациклический орграф G с произвольными весами c: E(G)

→ R и s, t  V(G).
Показать, как

Слайд 9Алгоритм Дейкстры
Input: Орграф G, веса c: E(G) → R+ и

вершина s V(G).
Output: Кратчайшие пути из s во все

Слайд 10Алгоритм Дейкстры (2)
Теорема 5.3 (Дейкстра [1959])
Алгоритм Дейкстры находит

Слайд 11Скетч доказательства
Докажем, что следующие утверждения верны каждый раз

когда выполняется шаг 2 алгоритма.
a) Для всех v 

Слайд 12Алгоритм Дейкстры
Input: Орграф G, веса c: E(G) → R+ и

вершина s V(G).
Output: Кратчайшие пути из s во все

≤ l(w)
Пусть v вершина выбранная на шаге 2.
Для любых x

Слайд 16Алгоритм Дейкстры
Теорема 5.3 (Дейкстра [1959])
Алгоритм Дейкстры находит

Слайд 17Алгоритм Мура-Беллмана-Форда
Input: Орграф G, консервативные веса c: E(G) →

R и вершина s V(G).
Output: Кратчайшие пути из s

Слайд 18Алгоритм Мура-Беллмана-Форда(2)
Теорема 5.4 (Moore [1959], Bellman [1958], Ford [1956])
Алгоритм

Слайд 19Скетч доказательства
На каждой итерации алгоритма пусть

F
F  {(x,y)  E(G): x = p(y)}
Рассмотрим последнюю итерацию,

суммарный вес
Пусть на некоторой итерации в F образовался цикл C

ордерево с корнем в s.
b)  F ― ациклический.
Для всех

Слайд 23Индукция
Пусть P кратчайший s-x-путь с не более чем k дугами

и пусть (w,x) последняя дуга в P.
Тогда P[s,w] кратчайший s-w-путь

Слайд 24Алгоритм Мура-Беллмана-Форда
Теорема 5.4 (Moore [1959], Bellman [1958], Ford [1956])

Алгоритм Мура-Беллмана-Форда находит оптимальное решение за O(nm) операций.

Покажем, что этот

Слайд 25Допустимый потенциал
Определение 5.5. Пусть G ― орграф с весами c:

Слайд 26Допустимый потенциал (2)
Теорема 5.6
Пусть G ― орграф

Слайд 27Доказательство
Если  допустимый потенциал, то для каждого цикла C:

 веса

консервативны.
Пусть веса консервативны, добавим новую вершину s и соединим ее

Слайд 28Допустимый потенциал
Следствие 5.7
Дан орграф G с

Слайд 29Задача «Все Пары Кратчайших путей»
Дано: орграф G, веса c: E(G)

→ R.
Найти число lst и вершины pst для всех s,

Слайд 30Задача «Все Пары Кратчайших путей» (2)

Теорема 5.8
Задача «Все Пары

Слайд 31Алгоритм Флойда-Уоршелла
Input: Орграф G с V(G) = {1,...,n} и

консервативные веса c: E(G) → R.
Output: Матрицы (lij)1≤i,j≤n

Слайд 32Шаг 2
For j  1 to n

do:
For i 

Слайд 33Алгоритм Флойда-Уоршелла (2)

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

Слайд 34Идея доказательства
Пусть алгоритм использовал во внешнем цикле (For) вершины j

Слайд 35Индукция: j0 → j0 + 1
j=j0+1
i
k
{1, 2, …, j0}
Для любых

i и k при выполнения шага 2
для j =

Слайд 36Метрическое замыкание
Определение 5.10
Дан связный граф G с весами

c: E(G) → R+.
Метрическим замыканием (G, c) называется пара

Слайд 37Метрическое замыкание (2)
Следствие 5.11
Пусть G ― связный

Слайд 38Задача «Минимальный усредненный Цикл»

Дано: орграф G, веса c: E(G) →

R.
Найти цикл C, усредненный вес которого c(E(C))/|E(C)| минимален, или показать

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

рассматривать только сильно связные графы.
Достаточно существования одной вершины из которой

Слайд 40Теорема Карпа
Теорема 5.12 (Karp [1978])

Пусть G ― орграф с весами

c: E(G) → R. Пусть s V(G) так,
что каждая вершина

Слайд 41Идея доказательства
Докажем, что если μ(G) = 0 то

Пусть G ―

Слайд 42Доказательство
Покажем, что существует такое x, что Fn(x) = l(x).
μ(G) =

0  существует цикл C нулевого веса.
Пусть w  C

Слайд 43Алгоритм «Минимальный усредненный Цикл»
Input: Орграф G, веса c: E(G) →

R.
Output: Цикл C с минимальным усредненным весом или информация,

Слайд 44Алгоритм «Минимальный усредненный Цикл»
Следствие 5.13(Karp [1978])
Алгоритм

Слайд 45Упражнение 7.2
Дан орграф G с произвольными весами

Слайд 46Упражнение 7.3
Дан орграф G с s, t  V(G). Пусть

Слайд 47Упражнение 7.4
Пусть G ― орграф с консервативными весами c: E(G)

Слайд 48Упражнение 7.5
Пусть G полный граф и c: E(G) → R+.