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

Кратчайшие пути в графе

Содержание

28.04.2014Кратчайшие пути 1Кратчайшие пути в графеПуть p в графе G = (V, E): p: u ⇒ v ≡ u = u1 → u2 → u3 → … → uk =

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

Слайд 128.04.2014
Кратчайшие пути 1
Лекция 11.2
Раздел: Алгоритмы на графах
Тема лекции:
Кратчайшие пути

в графе
Построение и анализ алгоритмов

28.04.2014Кратчайшие пути 1Лекция 11.2Раздел: Алгоритмы на графахТема лекции: Кратчайшие пути в графе Построение и анализ алгоритмов

Слайд 228.04.2014
Кратчайшие пути 1
Кратчайшие пути в графе
Путь p в графе G

= (V, E):
p: u ⇒ v ≡ u

= u1 → u2 → u3 → … → uk = v
Взвешенный граф G = (V, E, W),
где w(i, j) = w(vi, vj) - произвольны.
Длина пути:

p: u ⇒ v, p ∈ P(u, v) – множество путей между u и v

Приложения… W(u, v) = − log2 Prob(u, v)

28.04.2014Кратчайшие пути 1Кратчайшие пути в графеПуть p в графе G = (V, E): p: u ⇒ v

Слайд 328.04.2014
Кратчайшие пути 1
Вычисление расстояний и нахождение путей
Пусть вычислены все расстояния

d (u, v),
в т.ч. d (s, t).
Как найти

путь p: s ⇒ t ?

u

d (s, t) = d (s, u) + w (u, t)

Часть кратчайшего пути тоже кратчайший путь! v1~>vi~>vj~>vk (1 ≤ i ≤ j ≤ k)

28.04.2014Кратчайшие пути 1Вычисление расстояний и нахождение путейПусть вычислены все расстояния d (u, v), в т.ч. d (s,

Слайд 428.04.2014
Кратчайшие пути 1
Пример
2 – вес ребра w(i, j)
[1] –

расстояние d(u,v)
[8] = 4 + [4]

28.04.2014Кратчайшие пути 1Пример2 – вес ребра w(i, j) [1] – расстояние d(u,v)[8] = 4 + [4]

Слайд 528.04.2014
Кратчайшие пути 1
Пример
[4] = − 4 + [8]
[8] = 5

+ [3]
[3] = 3 + [0]

28.04.2014Кратчайшие пути 1Пример[4] = − 4 + [8][8] = 5 + [3][3] = 3 + [0]

Слайд 628.04.2014
Кратчайшие пути 1
Алгоритм нахождения кратчайшего пути по расстояниям между вершинами


/*Дано:
s, t – фиксированные вершины; s, t ∈V;
DL [ *

] – расстояния от вершины s до каждой вершины графа; DL[v]=d(s,v);
W[u, v] – матрица весов ребер, u, v ∈V;
Результат: St – стек, содержащий кратчайший путь от s до t,
т.е. последовательность вершин s=v0, v1, … , vk=t
*/
Create(st); st ← t; v = t;
while (v != s) {
u = вершина, для которой DL[v]=DL[u]+W[u,v];
St ← u;
v=u;
}
28.04.2014Кратчайшие пути 1Алгоритм нахождения кратчайшего пути по расстояниям между вершинами /*Дано:s, t – фиксированные вершины; s,

Слайд 728.04.2014
Кратчайшие пути 1
Алгоритм нахождения кратчайшего пути продолжение
Детализация строки
u = вершина,

для которой DL[v]=DL[u]+W[u,v];

Встать в начало Adj_In[v];
do
u = очередной элемент

из Adj_In[v];
while (d (s, t) != d (s, u) + w [ u, t ])

Adj_In[v] – список смежности входящих ребер
Adj_Out[v] – список смежности исходящих ребер

Adj_In[v]

Adj_Out[v]

Сложность
O(m)

28.04.2014Кратчайшие пути 1Алгоритм нахождения кратчайшего пути продолжениеДетализация строкиu = вершина, для которой DL[v]=DL[u]+W[u,v];Встать в начало Adj_In[v];do

Слайд 828.04.2014
Кратчайшие пути 1
Задачи вычисления длин кратчайших путей (расстояний)
Стартовая вершина s

фиксирована, конечная вершина t фиксирована. Найти d (s, t).
Стартовая вершина

s фиксирована. Найти d (s, v) для ∀ v ∈ V \ s.
Найти d (s, t) : ∀ s, t ∈ V & (s ≠ t ). Т.е. найти расстояния между всеми парами вершин.

Замечание: неизвестен ни один алгоритм решения задачи 1, который был бы более эффективным, чем известные алгоритмы, решающие задачу 2
28.04.2014Кратчайшие пути 1Задачи вычисления длин кратчайших путей (расстояний)Стартовая вершина s фиксирована, конечная вершина t фиксирована. Найти d

Слайд 928.04.2014
Кратчайшие пути 1
Задачи вычисления расстояний от фиксированной вершины
Общая схема большинства

алгоритмов:
рассматриваются временные пометки вершин dl [v], которые являются верхними

ограничениями для расстояний: dl [v] ≥ d (s, v) .
Улучшение оценки dl [v]:
void Relax (vert u, vert v)
// релаксация (ослабление) ребра u → v
{ if (dl [v] > dl [u] + W [ u, v ] ) dl [v] = dl [u] + W [ u, v ];
} //Relax
т.е. dl [v] := min (dl [v], dl [u] + W [ u, v ])
28.04.2014Кратчайшие пути 1Задачи вычисления расстояний от фиксированной вершиныОбщая схема большинства алгоритмов: рассматриваются временные пометки вершин dl [v],

Слайд 1028.04.2014
Кратчайшие пути 1
Релаксация (ослабление) ребра u → v
1
dl [u]
dl [v]
w

[u,v]
dl [u]
dl [v]
w [u,v]
Relax (u, v);
for (∀u ∈ Adj_In[v]) Relax(u,

v);

dl [a]

dl [b]

w [b,v]

w [a,v]

Релаксация входящих ребер относительно вершины v

28.04.2014Кратчайшие пути 1Релаксация (ослабление) ребра u → v1dl [u]dl [v]w [u,v]dl [u]dl [v]w [u,v]Relax (u, v);for (∀u

Слайд 1128.04.2014
Кратчайшие пути 1
Релаксация входящих ребер относительно вершины v :
for (∀u

∈ Adj_In[v]) Relax(u, v);
В результате
dl [v] = min (

dl [u] + W [ u, v ] ⎢ ∀u ∈ Adj_In[v] )
Инициализация: dl [v] = W [ s, v ] или dl [v] = ∞, dl [s] = 0.
Утверждение 1.
Если dl [v] = d (s, v), то релаксация не изменит dl [v] .
Утверждение 2.
Если u лежит на кратчайшем пути s ⇒ v и dl [u] = d (s, u), то после Relax(u, v) будет dl [v] = d (s, v).

Задачи вычисления расстояний от фиксированной вершины

28.04.2014Кратчайшие пути 1Релаксация входящих ребер относительно вершины v :for (∀u ∈ Adj_In[v]) Relax(u, v);В результате dl [v]

Слайд 12Продолжение на лекции 5 мая
28.04.2014
Кратчайшие пути 1

Продолжение на лекции 5 мая28.04.2014Кратчайшие пути 1

Слайд 13

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

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

Слайд 14
Алгоритм Дейкстры
(Dijkstra E.W. - 1959)

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

Алгоритм Дейкстры (Dijkstra E.W. - 1959)28.04.2014Кратчайшие пути 1

Слайд 1528.04.2014
Кратчайшие пути 1

Алгоритм Дейкстры
W [ *, * ] ≥ 0

Идея

алгоритма: V = S + T, S ∩ T=

∅
Инвариант:
( ∀ v∈S : DL[v] = d(s,v) ) &
( ∀ v∈T : DL[v] = длина кратчайшего из тех путей из s в v, в которых все вершины, кроме v, принадлежат множеству S )













S

T

s

Вершина u с минимальной пометкой

S:=S+{u}; T:=T \ {u}

28.04.2014Кратчайшие пути 1Алгоритм ДейкстрыW [ *, * ] ≥ 0Идея алгоритма: V = S + T,

Слайд 1628.04.2014
Кратчайшие пути 1

for (∀ v ∈V) DL[v] =W[s,v];
DL[s] =0;
T

= V \ {s}; // S = {{s}}
while

(T ≠ ∅) {
u = вершина x∈T, такая, что DL[x] = min { DL[p] : p ∈T };
T =T \ {u}; // S =S+{u}
for (∀ v ∈T) Relax (u,v);
} //while

Алгоритм Дейкстры

Дано: Орграф G= с выделенным источником s∈V;
W[u, v] – матрица весов дуг, u, v ∈V; W[u, v] ≥ 0
Результат: Расстояния от источника s до всех вершин графа DL[v]=d(s,v), v ∈V;

DL[v] = min { DL[v], DL[u]+W[u,v] }

28.04.2014Кратчайшие пути 1for (∀ v ∈V) DL[v] =W[s,v];DL[s] =0; T = V \ {s}; // S

Слайд 1728.04.2014
Кратчайшие пути 1
Пример

28.04.2014Кратчайшие пути 1Пример

Слайд 1828.04.2014
Кратчайшие пути 1
Пример

28.04.2014Кратчайшие пути 1Пример

Слайд 1928.04.2014
Кратчайшие пути 1

Корректность алгоритма: см. инвариант цикла while;
от противного
Алгоритм

Дейкстры



T
s
u
u′


Пусть u = arg min { DL[p] : p ∈T

}; но DL[u] > d(s,u).
Тогда ∃ u′ ∈T : DL[u′ ] = d(s,u′ ) ≤ d(s,u) < DL[u] !
(и u′ - первая вершина из T на пути s ⇒ u)
(противоречие) Сложность O (n 2)
28.04.2014Кратчайшие пути 1Корректность алгоритма: см. инвариант цикла while; от противногоАлгоритм ДейкстрыTsuu′Пусть u = arg min { DL[p]

Слайд 2028.04.2014
Кратчайшие пути 1
1) Множество T представляется
пирамидой Heap(T) с приоритетами

DL[v];
при этом Inv Heap(T): (∀u∈T:

(u=отец (v)) → (DL[u] ≤ DL[v]) ).
Тогда min(T) – в корне Heap(T), и исключение u из T есть удаление корня Heap(T) с восстановлением пирамидальности.
2) Используются списки смежности AdjOut[*].
Тогда обновление DL[v] после выбора вершины u реализуется следующим образом:
for (∀v∈ AdjOut[u])
if (DL[u] + W[u,v] < DL[v]) {
DL[v] = DL[u]+W[u,v];
Восстановить пирамидальность Heap(T) вверх от узла v;
}

Алгоритм Дейкстры (модификация O(m log n) )






Вершина u с минимальной пометкой

Каждая дуга графа анализируется один раз (!) и может вызвать действие O(log n)

28.04.2014Кратчайшие пути 11) Множество T представляется пирамидой Heap(T) с приоритетами DL[v]; при этом Inv Heap(T):

Слайд 21Следующий
Алгоритм Форда-Беллмана

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

СледующийАлгоритм Форда-Беллмана 28.04.2014Кратчайшие пути 1

Слайд 2228.04.2014
Кратчайшие пути 1
Алгоритм Форда-Беллмана
нахождения расстояний от источника
до остальных

вершин в графе,
не содержащем контуров отрицательной длины

Дано:
Орграф G=

с выделенным источником s∈V; ⎢V ⎢= n ;
W[u, v] – матрица весов дуг, u, v ∈V;
(граф не содержит контуров отрицательной длины)
Результат:
Расстояния от источника s до всех вершин графа
DL[v] = d(s,v), v ∈V;
28.04.2014Кратчайшие пути 1Алгоритм Форда-Беллмана нахождения расстояний от источника до остальных вершин в графе, не содержащем контуров отрицательной

Слайд 230
28.04.2014
Кратчайшие пути 1
Алгоритм Форда-Беллмана
Пример непригодности алгоритма Дейкстры при произвольных весах
b
2
1
Но

Relax (b, c) дает DL[c] = 0 !!!

028.04.2014Кратчайшие пути 1Алгоритм Форда-БеллманаПример непригодности алгоритма Дейкстры при произвольных весахb21Но Relax (b, c) дает DL[c] = 0

Слайд 2428.04.2014
Кратчайшие пути 1
for (∀ v ∈ V) DL[v] =W[s,v];


DL[s] = 0;
for (k=1; k


for (∀ v ∈ V \ {s})
for (∀ u ∈ V) Relax (u, v);

Алгоритм Форда-Беллмана

DL[v] = min { DL[v], DL[u]+W[u,v] }

Сложность O (n 3)

28.04.2014Кратчайшие пути 1for (∀ v ∈ V) DL[v] =W[s,v]; DL[s] = 0; for (k=1; k

Слайд 2528.04.2014
Кратчайшие пути 1
Вариант сложности O (nm)
for (∀ v ∈ V)

DL[v]=W[s,v];
DL[s] =0;
for (k=1; k

(∀ e ∈ E) Relax (u, v); //e=(u, v)

Алгоритм Форда-Беллмана

Примечание: если ещё раз (дополнительно) выполнить тело цикла “for (k=1; …)” и проверить уменьшение в Relax, то можно обнаружить в графе цикл отрицательной длины (в обоих вариантах)

28.04.2014Кратчайшие пути 1Вариант сложности O (nm)for (∀ v ∈ V) DL[v]=W[s,v]; DL[s] =0;for (k=1; k

Слайд 2628.04.2014
Кратчайшие пути 1
Пример. n = 6

Шаг 0

28.04.2014Кратчайшие пути 1Пример. n = 6 Шаг 0

Слайд 2728.04.2014
Кратчайшие пути 1
Пример. n = 6

Шаг 1
(a,b)
(a,d)
(a,e)
(b,c)
(b,d)
(d,e)
(d,f)
(e,f)*
(c,d)
(c,f)
(f,c)

28.04.2014Кратчайшие пути 1Пример. n = 6 Шаг 1(a,b)(a,d)(a,e)(b,c)(b,d)(d,e)(d,f)(e,f)*(c,d)(c,f)(f,c)

Слайд 2828.04.2014
Кратчайшие пути 1
Пример. n = 6

Шаг 2
(a,b)
(a,d)
(a,e)
(b,c)
(b,d)
(d,e)
(d,f)
(e,f)
(c,d)
(c,f)
(f,c)

28.04.2014Кратчайшие пути 1Пример. n = 6 Шаг 2(a,b)(a,d)(a,e)(b,c)(b,d)(d,e)(d,f)(e,f)(c,d)(c,f)(f,c)

Слайд 2928.04.2014
Кратчайшие пути 1
Пример. n = 6

Шаг 3
(a,b)
(a,d)
(a,e)
(b,c)
(b,d)
(d,e)
(d,f)
(e,f)
(c,d)
(c,f)
(f,c)

28.04.2014Кратчайшие пути 1Пример. n = 6 Шаг 3(a,b)(a,d)(a,e)(b,c)(b,d)(d,e)(d,f)(e,f)(c,d)(c,f)(f,c)

Слайд 3028.04.2014
Кратчайшие пути 1
Индуктивное утверждение (“инвариант”) цикла
for (k=1; k

2); k++) {…} :
P( [1..k) ) ≡ ( d(s,v) ≤

DL[v] ≤ d[ k | v ] ) - инвариант точки входа тела цикла,
P( [1..k] ) ≡ ( d(s,v) ≤ DL[v] ≤ d[k+1| v ] ) - инвариант точки выхода тела цикла,
где d[ k | v ] – длина кратчайшего из путей из s в v, содержащих не более k дуг.

Рекуррентное соотношение:
d[k+1| v ] = min {d[ k | u ] + W[u,v] ⎢ u ∈ V }

Алгоритм Форда-Беллмана





s

u

v

Сами величины d[k|v] в алгоритме не используются!
Они нужны только для записи утверждений.


Типичное соотношение динамического программирования

28.04.2014Кратчайшие пути 1Индуктивное утверждение (“инвариант”) цикла for (k=1; k

Слайд 3128.04.2014
Кратчайшие пути 1
Если P( [1..k) ) и P( [1..k]

) действительно инварианты, то для остановки необходимо, чтобы после k

итераций было бы k + 1 = n − 1 (т.к. путь без циклов в графе с n вершинами может иметь не более n − 1 дуг ).
Отсюда k = n − 2
Покажем, что действительно тело внешнего цикла переводит P( [1..k) ) в P( [1..k] )

Корректность алгоритма Форда-Беллмана

28.04.2014Кратчайшие пути 1 Если P( [1..k) ) и P( [1..k] ) действительно инварианты, то для остановки необходимо,

Слайд 3228.04.2014
Кратчайшие пути 1
После очередной итерации
d(s,v) ≤ DL[v] ≤ { по

алгоритму, с учетом того, что пометки DL[u] могли уже уменьшиться

на предыдущих шагах циклов внутри одной итерации по k }
≤ min {DL[u] + W[u,v] ⎢ u ∈ V } ≤
≤ min {d[ k | u ] + W[u,v] ⎢ u ∈ V } = d[ k + 1 | u ]

Корректность алгоритма Форда-Беллмана

по предположению индукции


новая

старая



28.04.2014Кратчайшие пути 1После очередной итерацииd(s,v) ≤ DL[v] ≤ { по алгоритму, с учетом того, что пометки DL[u]

Слайд 3328.04.2014
Кратчайшие пути 1
Кратчайшие пути между всеми парами вершин
См. лекцию 12

28.04.2014Кратчайшие пути 1Кратчайшие пути между всеми парами вершинСм. лекцию 12

Слайд 34Примечание
28.04.2014
Кратчайшие пути 1

Примечание 28.04.2014Кратчайшие пути 1

Слайд 3528.04.2014
Кратчайшие пути 1
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ

ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ

28.04.2014Кратчайшие пути 1КОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ

Похожие презентации

Топографическая съемка Топографическая съемка 719
М.А. Булгаков М.А. Булгаков 479
Форма черепа и его изменчивость Форма черепа и его изменчивость 272
Субстратное фосфорилирование. Виды брожения Субстратное фосфорилирование. Виды брожения 236
Исаак Ньютон Исаак Ньютон 136
Серебряный век русской культуры Серебряный век русской культуры 210
МБОУ СОШ с. Бессоновка МБОУ СОШ с. Бессоновка 245
Школьный предмет История в контексте действующей нормативной базы Бакаляр Школьный предмет История в контексте действующей нормативной базы Бакаляр 196
ТЕОРИЯ САЛЛИВАНА Презентацию подготовили студентки группы УПБО-03-18 Азизова ТЕОРИЯ САЛЛИВАНА Презентацию подготовили студентки группы УПБО-03-18 Азизова 233
Фотоотчет Фотоотчет 203
Д ә р у м е н д е р ә л ем ін е с а я х а т Д ә р у м е н д е р ә л ем ін е с а я х а т 261
Муниципальное бюджетное общеобразовательное учреждение средняя Муниципальное бюджетное общеобразовательное учреждение средняя 169
В.ф.Одоевский «Мороз иВАНОВИЧ» В.ф.Одоевский «Мороз иВАНОВИЧ» 562
Солдат войны не выбирает… (30-ая годовщина окончания войны в Афганистане), 2019 Солдат войны не выбирает… (30-ая годовщина окончания войны в Афганистане), 2019 212
Оксиды Оксиды 336
У кого есть надежда-есть всё. Здоровье - важнейший фактор работоспособности и У кого есть надежда-есть всё. Здоровье - важнейший фактор работоспособности и 176
СОБРАНИЕ 14.09.2020 СОБРАНИЕ 14.09.2020 181
Имущественный комплекс земельный участок 1,6 га со зданиями, расположенный по Имущественный комплекс земельный участок 1,6 га со зданиями, расположенный по 197
Природа, растения и животные Белгородской области Природа, растения и животные Белгородской области 261
Без пяти лет диабет (факторы риска, симптомы, профилактика) Без пяти лет диабет (факторы риска, симптомы, профилактика) 160

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.

Для правообладателей

Яндекс.Метрика