Олимпиады по программированию

olympiads.ru

МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Занятие 7. Графы. Поиск кратчайшего пути. Алгоритм Флойда.

Пусть дан взвешенный граф с N вершинами и M ребрами. Требуется найти кратчайшие расстояния между всеми парами. Эта задача может быть решена с помощью алгоритма Флойда.

Рассмотрим два случая:

I. В графе нет циклов отрицательного веса.

В основе алгоритма Флойда лежит метод динамического программирования. Пусть A^k - матрица размера NxN с элементами a^k_i,j, где a^k_i,j - длина кратчайшего пути между вершинами i и j, проходящего через вершины с номерами меньше либо равными k (не считая начальной и конечной вершин). Тогда A⁰ - матрица смежности нашего графа, Aⁿ - искомая матрица кратчайших расстояний. Найдем a^k_i,j, зная A^k-1. Заметим, что в кратчайшем пути между вершинами i и j, содержащем вершины с номерами от 1 до k (т.е. соответсвующем a^k_i,j) вершина k может либо встречаться, либо нет. Значит a^k_i,j = min(a^k-1_i,j , a^k-1_i,k + a^k-1_k,j).

Один из вариантов реализации алгоритма Флойда выглядит так:
   for k := 1 to n do
     for i := 1 to n do
       for j := 1 to n do
         if a[k,i,j] > a[k-1,i,k] + a[k-1,k,j] then
           a[k,i,j] := a[k-1,i,k] + a[k-1,k,j];

Пусть у нас есть кратчайший путь из вершины i в вершину k. Заметим тогда, что в этом пути вершина k не может встречаться среди промежуточных вершин. Действительно, пусть это не так, тогда в нашем графе найдется цикл отрицательного веса, а этого по условию быть не может. В наших обозначениях это выглядит так: a[k,i,k]=a[k-1,i,k] и a[k,k,j]=a[k-1,k,j] для любых i и j. Значит алгоритм Флойда можно изменить следующим образом:
   for k := 1 to n do
     for i := 1 to n do
       for j := 1 to n do
         if a[i,j] > a[i,k] + a[k,j] then
           a[i,j] := a[i,k] + a[k,j];

II. В графе есть циклы отрицательного веса.

В этом случае между некоторыми парами вершин может быть сколь угодно короткий путь. Найи такие пары несложно по матрице "кратчайших" путей, посторенных алгоритмом Флойда. Имеют место утверждения:

1. Если существует цикл отрицательного веса, проходящий через вершину i, то a_i,i будет меньше 0.
2. Между парой вершин (i,j) существует сколь угодно малый путь тогда и только тогда, когда существует путь из i в j, содержащий цикл отрицательного веса или, иными словами, существует вершина k такая, что существует путь из i в k, из k в j и существует цикл отрицательного веса, проходящий через k