На этом шаге мы рассмотрим алгоритм Флойда.

    Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i, j) равен расстоянию d_ij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.

    Покажем сначала основную идею метода Флойда. Пусть есть три узла i, j и k и заданы расстояния между ними (рис. 1). Если выполняется неравенство d_ij + d_jk < d_ik, то целесообразно заменить путь i -> k путем i -> j -> k. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

Рис.1. Треугольный оператор

    Алгоритм Флойда требует выполнения следующих действий.

    Шаг 0. Определяем начальную матрицу расстояния D₀ и матрицу последовательности узлов S₀. Диагональные элементы обеих матриц помечаются знаком "-", показывающим, что эти элементы в вычислениях не участвуют. Полагаем k = 1:

Рис.2. Начальная ситуация

    Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам d_ij матрицы D_k-1. Если выполняется неравенство d_ik + d_kj < d_ij, (i <> k, j <> k, i <> j), тогда выполняем следующие действия:

• создаем матрицу D_k путем замены в матрице D_k-1 элемента d_ij на сумму d_ik + d_kj,
• создаем матрицу S_k путем замены в матрице S_k-1 элемента s_ij на k. Полагаем k = k + 1 и повторяем шаг k.

    Поясним действия, выполняемые на k-м шаге алгоритма, представив матрицу D_k-1 так, как она показана на рисунке 3. На этом рисунке строка k и столбец k являются ведущими. Строка i - любая строка с номером от 1 до k - 1, а строка p - произвольная строка с номером от k + 1 до n. Аналогично столбец j представляет любой столбец с номером от 1 до k - 1, столбец q - произвольный столбец с номером от k + 1 до n. Треугольный оператор выполняется следующим образом. Если сумма элементов ведущих строки и столбца (показанных в квадратах) меньше элементов, находящихся в пересечении столбца и строки (показанных в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется на сумму расстояний, представленных ведущими элементами:

Рис.3. Иллюстрация алгоритма Флойда

    После реализации n шагов алгоритма определение по матрицам D_n и S_n кратчайшего пути между узлами i и j выполняется по следующим правилам.

1. Расстояние между узлами i и j равно элементу d_ij в матрице D_n.
2. Промежуточные узлы пути от узла i к узлу j определяем по матрице S_n. Пусть s_ij = k, тогда имеем путь i -> k -> j. Если далее s_ik = k и s_kj = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.

Рис.4. Пример сети

    Шаг 0. Начальные матрицы D₀ и S₀ строятся непосредственно по заданной схеме сети. Матрица D₀ симметрична, за исключением пары элементов d₃₅ и d₅₃, где d₅₃ равно бесконечности, поскольку невозможен переход от узла 5 к узлу 3:

Рис.5. Начальное состояние

    Шаг 1. В матрице D₀ выделены ведущие строка и столбец (k = 1). Двойной рамкой представлены элементы d₂₃ и d₃₂, единственные среди элементов матрицы D₀, значения которых можно улучшить с помощью треугольного оператора. Таким образом, чтобы на основе матриц D₀ и S₀ получить матрицы D₁ и S₁, выполняем следующие действия.

1. Заменяем d₂₃ на d₂₁ + d₁₃ = 3 + 10 = 13 и устанавливаем s₂₃ = 1.
2. Заменяем d₃₂ на d₃₁ + d₁₂ = 10 + 3 = 13 и устанавливаем s₃₂ = 1.

    Матрицы D₁ и S₁ имеют следующий вид:

Рис.6. Матрицы D₁ и S₁

    Шаг 2. Полагаем k = 2; в матрице D₁ выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матрицы D₁ и S₁, выделенным двойной рамкой. В результате получаем матрицы D₂ и S₂:

Рис.7. Матрицы D₂ и S₂

    Шаг 3. Полагаем k = 3; в матрице D₂ выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матрицы D₂ и S₂, выделенным двойной рамкой. В результате получаем матрицы D₃ и S₃:

Рис.8. Матрицы D₃ и S₃

    Шаг 4. Полагаем k = 4, ведущие строка и столбец в матрице D₃ выделены. Получаем новые матрицы D₄ и S₄:

Рис.9. Матрицы D₄ и S₄

    Шаг 5. Полагаем k = 5, ведущие строка и столбец в матрице D₄ выделены. Никаких действий на этом шаге не выполняем; вычисления закончены.

    Конечные матрицы D₄ и S₄ содержат всю информацию, необходимую для определения кратчайших путей между любыми двумя узлами сети. Например, кратчайшее расстояние между узлами 1 и 5 равно d₁₅ = 12.

    Для нахождения соответствующих маршрутов напомним, что сегмент маршрута (i, j) состоит из ребра (i, j) только в том случае, когда s_ij = j. В противном случае узлы i и j связаны, по крайней мере, через один промежуточный узел. Например, поскольку s₁₅ = 4 и s₄₅ = 5, сначала кратчайший маршрут между узлами 1 и 5 будет иметь вид 1->4->5. Но так как s₁₄ не равно 4, узлы 1 и 4 в определенном пути не связаны одним ребром (но в исходной сети они могут быть связаны непосредственно). Далее следует определить промежуточный узел (узлы) между первым и четвертым узлами. Имеем s₁₄ = 2 и s₂₄ = 4, поэтому маршрут 1->4 заменяем 1->2->4. Поскольку s₁₂ = 2 и s₂₄ = 4, других промежуточных узлов нет. Комбинируя определенные сегменты маршрута, окончательно получаем следующий кратчайший путь от узла 1 до узла 5: 1->2->4->5. Длина этого пути равна 12 километрам.

    Приведем текст программы, реализующей алгоритм Флойда.

#include <iostream.h>
#define TRUE 1
#define FALSE 0
#define MaxNodes 5  //Количество вершин.
//Описание типа узла стека.
typedef struct Zveno *svqz;
typedef struct Zveno
{
  int Element;
  svqz Sled;
};

class Spisok
{
  private:
         int Mas[MaxNodes][MaxNodes];  //Матрица весов дуг.
         int DD[MaxNodes][MaxNodes];   //Матрица расстояний.
         int SS[MaxNodes][MaxNodes];   //Матрица последовательных узлов.
         svqz Stack; //Указатель на рабочий стек.
         void UDALENIE (svqz *, int *);
         void W_S (svqz *, int);
         void Small_Put (int,int);
  public:
         Spisok() {Stack = NULL;}
         void Vvod_Ves();
         void Reshenie ();
};

void main()
{
  Spisok A;

  A.Vvod_Ves();
  A.Reshenie();
}

void Spisok::Small_Put (int one, int two)
//Нахождение кратчайшего пути.
{
  svqz St=NULL; //Указатель на вспомогательный стек.
  svqz UkZv;
  int Flag=FALSE; //Флаг построения кратчайшего пути.
  int elem1,elem2,k;
  //Помещение в стек конечной и начальной вершин.
  W_S (&Stack,two);
  W_S (&Stack,one);
  while (!Flag)
  {
    //Извлекли верхних два элемента.
    UDALENIE(&Stack,&elem1);
    UDALENIE(&Stack,&elem2);
    if (SS[elem1][elem2]==elem2) //Если есть путь...
      if (elem2==two) //и это конечный узел...
      {
       Flag = TRUE;   //то кратчайший путь найден.
       W_S (&St,elem1);
       W_S (&St,elem2);
      }
      else //и это не конечный узел...
      {
       W_S (&St,elem1); //В вспомогательный стек.
       W_S (&Stack,elem2); //Обратно в рабочий стек.
      }
    else //Если пути нет.
    {
      W_S (&Stack,elem2); //Обратно в рабочий стек.
      k = SS[elem1][elem2];
      W_S (&Stack,k);     //Запомнить промежуточную вершину.
      W_S (&Stack,elem1); //Обратно в рабочий стек.
    }
  }
  UkZv = St;
  while ( UkZv != NULL )
  {  cout << (UkZv->Element+1) << " "; 
     UkZv = UkZv->Sled;  }
  cout << endl;
}

void Spisok::W_S (svqz *stk, int Elem)
//Помещение Elem в стек stk.
{
  svqz q=new (Zveno);
  (*q).Element = Elem; 
  (*q).Sled = *stk; *stk = q;
}

void Spisok::UDALENIE (svqz *stk, int *Klad)
//Удаление звена из стека, заданного указателем *stk.
//Значение информационного поля удаляемого звена сохраня-
//ется в параметре Klad.
{
  svqz q;

  if (*stk==NULL) cout<<"Попытка выбора из пустого стека!\n";
  else
	{ *Klad = (**stk).Element;
	  q = *stk; *stk = (**stk).Sled; delete q; }
}


void Spisok::Vvod_Ves()
//Ввод матрицы весов дуг заданного графа.
{
  cout << "Вводите элементы матрицы весов дуг по строкам:\n";
  for (int i=0;i<MaxNodes;i++)
   for (int j=0;j<MaxNodes;j++)
     {
       cout << "Введите Mas[" << (i+1) << "," << (j+1) << "]: "; 
       cin >> Mas[i][j];
     }
}

void Spisok::Reshenie()
{
  int one,two;
  int i,j;

  //Инициализация.
  for (i=0;i<MaxNodes;i++)
   for (j=0;j<MaxNodes;j++)
   {
     if (Mas[i][j]>0)  SS[i][j]=j;
     else SS[i][j]=0;
     DD[i][j]=Mas[i][j];
   }
   cout << "\nНачальная вершина: ";
   cin >> one; one--;
   cout << "Конечная вершина: ";
   cin >> two; two--;

   int ved=0;
   while (ved<MaxNodes)
   {
     for (i=0;i<MaxNodes;i++)
      for (j=0;j<MaxNodes;j++)
        if (i!=j && i!=ved && j!=ved &&
            DD[i][ved]>0 && DD[ved][j]>0) 
          if (DD[i][ved]+DD[ved][j]<DD[i][j] || DD[i][j]==0) 
          {
             DD[i][j]=DD[i][ved]+DD[ved][j];
             SS[i][j]=ved;
          }
          ved++;
   }
   i=one;
   if (SS[i][two]!=two && SS[i][two]!=0) 
     while (SS[i][two]!=two) 
     {
        j=SS[i][two];
        while (SS[i][j]!=j)  j=SS[i][j];
        i=j;
     }
     cout << "\nКратчайший путь (в обратном порядке): ";
     Small_Put (one, two);
     cout << "Длина минимального пути между этими вершинами: " << DD[one][two];
}

    Результат работы этой программы для сети, изображенной на рисунке 4, будет следующим:

Рис.10. Результат работы приложения

    На следующем шаге мы рассмотрим задачу о максимальном потоке.

Предыдущий шаг Содержание Следующий шаг