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

1.

ТЕОРИЯ ГРАФОВ
АЛГОРИТМЫ НА ГРАФАХ
ПРЕПОДАВАТЕЛЬ
ПРОФ. ИВАНИЛОВА Т.Н.

2.

ПОИСК МИНИМАЛЬНОГО ПУТИ В
НАГРУЖЕННОМ ГРАФЕ (ОРГРАФЕ)
(АЛГОРИТМ ФОРДА-БЕЛЛМАНА)
Орграф D называется нагруженным, если на множестве
дуг X определена весовая функция l: Х R.
l(x) – длина дуги х Х.
Для всякого пути π обозначим l(π) сумму длин дуг,
входящих в путь π, причем всякая дуга учитывается
столько раз, сколько она входит в путь
l(π) – длина пути в нагруженном орграфе D.
Аналогичные определения верны для нагруженного
графа G.
Путь в нагруженном орграфе D называется
минимальным (v ≠ w), если он имеет минимальную длину
среди всех путей D из v в w.

3.

4.

МАТРИЦА ДЛИН ДУГ (РЕБЕР) С(D) = [CIJ]
l (vi , v j ), если (vi , v j ) X
cij
,
если
(
v
,
v
)
X
i
j

5.

ПРИМЕР МАТРИЦЫ ДЛИН
РЕБЕР ГРАФА G

6.

Пусть D = (V, x), V = {v1, …, vn}, n 2. Введем в рассмотрение:
min l( v l , v i ) содержит не более k дуг
l L
(ik )
, таких путей нет.
λl(0) = 0, λi(0) = , i = 2, …, n.
где L – множество всех путей из v1 в vi

7.

ТЕОРЕМА
При i=2,…,n, k≥0 выполняется
(