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

Сентябрь 3, 2022

Главная
Алгебра
Кратчайшие пути в графе

Содержание

2. 28.04.2014 Кратчайшие пути 1 Кратчайшие пути в графе Путь p в графе G = (V, E):
3. 28.04.2014 Кратчайшие пути 1 Вычисление расстояний и нахождение путей Пусть вычислены все расстояния d (u, v),
4. 28.04.2014 Кратчайшие пути 1 Пример 2 – вес ребра w(i, j) [1] – расстояние d(u,v) [8]
5. 28.04.2014 Кратчайшие пути 1 Пример [4] = − 4 + [8] [8] = 5 + [3]
6. 28.04.2014 Кратчайшие пути 1 Алгоритм нахождения кратчайшего пути по расстояниям между вершинами /*Дано: s, t –
7. 28.04.2014 Кратчайшие пути 1 Алгоритм нахождения кратчайшего пути продолжение Детализация строки u = вершина, для которой
8. 28.04.2014 Кратчайшие пути 1 Задачи вычисления длин кратчайших путей (расстояний) Стартовая вершина s фиксирована, конечная вершина
9. 28.04.2014 Кратчайшие пути 1 Задачи вычисления расстояний от фиксированной вершины Общая схема большинства алгоритмов: рассматриваются временные
10. 28.04.2014 Кратчайшие пути 1 Релаксация (ослабление) ребра u → v 1 dl [u] dl [v] w
11. 28.04.2014 Кратчайшие пути 1 Релаксация входящих ребер относительно вершины v : for (∀u ∈ Adj_In[v]) Relax(u,
12. Продолжение на лекции 5 мая 28.04.2014 Кратчайшие пути 1
13. 28.04.2014 Кратчайшие пути 1
14. Алгоритм Дейкстры (Dijkstra E.W. - 1959) 28.04.2014 Кратчайшие пути 1
15. 28.04.2014 Кратчайшие пути 1 Алгоритм Дейкстры W [ *, * ] ≥ 0 Идея алгоритма: V
16. 28.04.2014 Кратчайшие пути 1 for (∀ v ∈V) DL[v] =W[s,v]; DL[s] =0; T = V \
17. 28.04.2014 Кратчайшие пути 1 Пример
18. 28.04.2014 Кратчайшие пути 1 Пример
19. 28.04.2014 Кратчайшие пути 1 Корректность алгоритма: см. инвариант цикла while; от противного Алгоритм Дейкстры T s
20. 28.04.2014 Кратчайшие пути 1 1) Множество T представляется пирамидой Heap(T) с приоритетами DL[v]; при этом Inv
21. Следующий Алгоритм Форда-Беллмана 28.04.2014 Кратчайшие пути 1
22. 28.04.2014 Кратчайшие пути 1 Алгоритм Форда-Беллмана нахождения расстояний от источника до остальных вершин в графе, не
23. 0 28.04.2014 Кратчайшие пути 1 Алгоритм Форда-Беллмана Пример непригодности алгоритма Дейкстры при произвольных весах b 2
24. 28.04.2014 Кратчайшие пути 1 for (∀ v ∈ V) DL[v] =W[s,v]; DL[s] = 0; for (k=1;
25. 28.04.2014 Кратчайшие пути 1 Вариант сложности O (nm) for (∀ v ∈ V) DL[v]=W[s,v]; DL[s] =0;
26. 28.04.2014 Кратчайшие пути 1 Пример. n = 6 Шаг 0
27. 28.04.2014 Кратчайшие пути 1 Пример. n = 6 Шаг 1 (a,b) (a,d) (a,e) (b,c) (b,d) (d,e)
28. 28.04.2014 Кратчайшие пути 1 Пример. n = 6 Шаг 2 (a,b) (a,d) (a,e) (b,c) (b,d) (d,e)
29. 28.04.2014 Кратчайшие пути 1 Пример. n = 6 Шаг 3 (a,b) (a,d) (a,e) (b,c) (b,d) (d,e)
30. 28.04.2014 Кратчайшие пути 1 Индуктивное утверждение (“инвариант”) цикла for (k=1; k P( [1..k) ) ≡ (
31. 28.04.2014 Кратчайшие пути 1 Если P( [1..k) ) и P( [1..k] ) действительно инварианты, то для
32. 28.04.2014 Кратчайшие пути 1 После очередной итерации d(s,v) ≤ DL[v] ≤ { по алгоритму, с учетом
33. 28.04.2014 Кратчайшие пути 1 Кратчайшие пути между всеми парами вершин См. лекцию 12
34. Примечание 28.04.2014 Кратчайшие пути 1
36. Скачать презентацию

Слайд 2

28.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)

Слайд 3

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

(u, v),
в т.ч. d (s, t).
Как найти путь p: s ⇒ t ?

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

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

Слайд 4

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

d(u,v)

[8] = 4 + [4]

Слайд 5

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

[3]

[3] = 3 + [0]

Слайд 6

28.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;
}

Слайд 7

28.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)

Слайд 8

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

Слайд 9

28.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 ])

Слайд 10

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

Слайд 11

28.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).

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

Слайд 12

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

Слайд 13

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

Слайд 14

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

Слайд 15

28.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 )

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

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

Слайд 16

28.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] }

Слайд 17

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

Слайд 18

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

Слайд 19

28.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)

Слайд 20

28.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)

Слайд 21

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

Слайд 22

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

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

Слайд 23

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

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

Слайд 24

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

0;
for (k=1; k<=(n − 2); k++)
for (∀ v ∈ V \ {s})
for (∀ u ∈ V) Relax (u, v);

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

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

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

Слайд 25

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

DL[s] =0;
for (k=1; k<=(n − 2); k++)
for (∀ e ∈ E) Relax (u, v); //e=(u, v)

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

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

Слайд 26

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

Слайд 27

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)

Слайд 28

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)

Слайд 29

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)

Слайд 30

28.04.2014
Кратчайшие пути 1
Индуктивное утверждение (“инвариант”) цикла
for (k=1; k<=(n − 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 }

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

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

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

Слайд 31

28.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] )

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

Слайд 32

28.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 ]

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

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

новая

старая

Слайд 33

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

Слайд 34

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

Содержание

28.04.2014Кратчайшие пути 1Кратчайшие пути в графеПуть p в графе G =

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

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

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

28.04.2014Кратчайшие пути 1Алгоритм нахождения кратчайшего пути по расстояниям между вершинами /*Дано:s,

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

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

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

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

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

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

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

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

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

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

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

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

28.04.2014Кратчайшие пути 1Корректность алгоритма: см. инвариант цикла while; от противногоАлгоритм ДейкстрыTsuu′Пусть

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

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

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

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

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

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

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

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)

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)

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)

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

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

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

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

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

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

28.04.2014
Кратчайшие пути 1
Кратчайшие пути в графе
Путь p в графе G =

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

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

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

28.04.2014
Кратчайшие пути 1
Алгоритм нахождения кратчайшего пути по расстояниям между вершинами
/*Дано:
s,

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

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

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

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

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

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

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

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

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

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

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

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

28.04.2014
Кратчайшие пути 1
Корректность алгоритма: см. инвариант цикла while;
от противного
Алгоритм Дейкстры
T
s
u
u′
Пусть

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

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

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

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

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

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

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

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)

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)

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)

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

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

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

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

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