Задача о кратчайшем пути

Пусть известен сетевой график (см. рисунок 1) всевозможных маршрутов из пункта 0 в n. Заданы неотрицательные числа l_ij – длина пути из n_i в n_j. Считается, что сеть сильно связана, т.е. существует путь между любыми двумя ее вершинами. Требуется определить кратчайший путь из пункта 0 в пункт n (в данном примере n=7).

Рис. 1

Алгоритм Форда:

1⁰. Помечаем вершину 0 индексом a₀.

2⁰. Помечаем в порядке нумерации все вершины сетевого графика следующим образом: a_j = min_i,j [a_i+l_ij], где i,j – номера вершин.

3⁰. Находим значение a_n – длину кратчайшего пути.

4⁰. Двигаясь от конца сетевого графика к началу, определяем дуги, входящие в кратчайший путь, как дуги, для которых min [a_j-a_i] = l_ij.

Решение:

1. a₀=0

2. a₁=l₀₁=1

a₂=min[0+4;1+2]=3

a₃=min[0+6;3+1]=4

a₄=min[3+5;4+2]=6

a₅=min[4+2;6+3]=6

a₆=min[6+1;1+7]=7

a₇=min[7+2;6+5;6+4]=9

3. Итак, a_n=a₇=9

4. Двигаясь от конца к началу, определяем дуги, входящие в кратчайший путь из условия min [a_j-a_i] = l_ij.

из 7: min[a₇-a₆; a₇-a₄; a₇-a₅]=min[9-7;9-6;9-6]=2, 76

из 6: min[a₆-a₄; a₆-a₁]=min[7-6;7-1]=1, 764

из 4: min[a₄-a₂; a₄-a₃]=min[6-3;6-4]=2, 7643

из 3: min[a₃-a₂; a₃-a₀]=min[4-1;4-0]=3, 76432

из 2: min[a₂-a₁; a₂-a₀]=min[3-1;3-0]=2, 764321

из 1: [a₁-a₀]=1, 7643210

Значит, кратчайший путь 0®1®2®3®4®6®7.

Длина пути a_n=9.