Лекции по дискретной математике. Ч.II. Комбинаторика, разостные уравнения, алгоритмы на графах. Гайдамака Ю.В - 54 стр.

UptoLike

ВУЗ: 

РУДН | Москва

Составители: 

Рубрика: 

Лекция 14. Нахождение расстояния между всеми парами
вершин. Алгоритм Уоршалла-Флойда. Связность
орграфов. Транзитивное замыкание.
Очевидно, что задачу определения расстояния между всеми па-
рами вершин можно решить, используя n(n-1) раз алгоритм Дейк-
стра. Однако, сложность такой процедуры будет составлять O(n
4
).
Существуют более эффективные алгоритмы, в частности, алго-
ритм Уоршалла и Флойда.
Рассмотрим орграф G=<V,E>, V={v
1
,…,v
n
}. Пусть
n,j,i
ij
)w(W
1=
=
- матрица весов графа. Пусть - длина кратчай-
шего из путей из v
)m(
ij
d
i
в v
j
с промежуточными вершинами в множест-
ве {v
1
,…,v
m
},
n,m 1=
. Тогда
ij
)(
ij
wd =
0
(14.1)
)dd,dmin(d
)m(
mj
)m(
im
)m(
ij
)m(
ij
111 −−−
+=
, n,m,j,i 1= (14.2)
Обоснование уравнения (14.2) следующее. Рассмотрим крат-
чайший путь из v
i
в v
j
с промежуточными вершинами из множества
{v
1
,…,v
m
}. Если этот путь не содержит v
m
, то d
ij
(m)
= d
ij
(m-1)
. Если же
он содержит v
m
, то деля путь на отрезки от v
i
до v
m
и от v
m
до v
j
по-
лучаем равенство d
ij
(m)
= d
im
(m-1)
+ d
mj
(m-1)
. Уравнения (14.1) и (14.2)
дают возможность вычислять расстояния D(v
i
,v
j
)=d
ij
(n)
для любых
1
≤
i,j
≤
n.
Алгоритм Уоршалла-Флойда.
Здесь D(v
i
,v
j
)=D[i,j].
begin
for i=1 to n do
for j=1 to n do D[i,j]=W[i,j];
for m:=1 to n do
for i:=1 to n do
for j:=1 to n do
D[i,j]:=min(D[i,j], D[i,m]+ D[m,j]
end
Сложность алгоритма Уоршалла-Флойда O(n
3
).
54

Страницы