На этом шаге мы рассмотрим алгоритм нахождения кратчайших путей между вершинами графа.

Алгоритм Уоршалла может быть модифицирован с целью получения матрицы, содержащей длины кратчайших путей между вершинами [1, с.441].

Идея этого алгоритма следующая [2,с.131]. Обозначим через d^(m)_ij длину кратчайшего из путей из v_i в v_j с промежуточными вершинами в множестве {v₁, ..., v_m}.

Тогда имеем следующие уравнения, объединенные в систему:

    d⁽⁰⁾_ij = a_ij
    d^(m)_ij = min(d^(m)_ij, d^(m)_im + d^(m)_mj)

Обоснование второго уравнения достаточно простое. Рассмотрим кратчайший путь из v_i в v_j c промежуточными вершинами из множества {v₁, ..., v_m,v_m+1}. Если этот путь не содержит v_m+1, то деля путь на отрезки от v_i до v_m+1 и от v_m+1 до v_j, получаем равенство

    d^(m+1)_ij = d^(m)_im + d^(m)_mj).

Вышеприведенные уравнения дают возможность легко вычислить расстояния

    d(v_i,v_j) = d⁽ⁿ⁾_ij, 1 <= i, j <= n.

Для машинной реализации алгоритма предположим, что A - матрица смежности графа. Заменим все нулевые элементы A на "бесконечность" или на некоторое "очень большое число", которое в данной матрице обозначим через B. Требуемая матрица длин минимальных путей формируется следующим алгоритмом, записанным на языке C++.

Программа. Вычисление матрицы минимальных длин путей.

#include <iostream.h>
#define MaxNodes 4
#define B 1000

class Warshall
{
  private:
    unsigned Adj[MaxNodes][MaxNodes]; //Матрица смежностей.
    unsigned C[MaxNodes][MaxNodes];   //Матрица достижимости.
  public:
    void Vvod();
    void MinDlin();
    void Vyvod();
};

void Warshall::Vvod()
//Ввод матрицы смежностей заданного графа и ее "исправление".
{
  //Ввод матрицы смежностей заданного графа.
  cout <<"Вводите элементы матрицы смежностей по строкам:\n";
  for (int i=0;i<MaxNodes;i++)
    for (int j=0;j<MaxNodes;j++)
     {
       cout <<"Введите Adj["<< (i+1) << "]["<< (j+1) << "]: ";
       cin >> Adj[i][j];
       if (Adj[i][j]==0) C[i][j] = B;
       else  C[i][j] = Adj[i][j];
     }
}

void Warshall::MinDlin()
//Вычисление матрицы минимальных длин путей.
{
  for (int k=0;k<MaxNodes;k++)
   for (int i=0;i<MaxNodes;i++)
    for (int j=0;j<MaxNodes;j++)
       if ( C[i][j]>C[i][k]+C[k][j] ) 
              C[i][j] = C[i][k]+C[k][j];
}

void Warshall::Vyvod()
//Вывод матрицы минимальных длин путей.
{
  cout << "Матрица минимальных длин путей:\n";
  for (int i=0;i<MaxNodes;i++)
  {
    for (int j=0;j<MaxNodes;j++)
      cout << C[i][j] << " ";
    cout << endl;
  }
}

void main()
{
  Warshall A;
  A.Vvod();
  A.MinDlin();
  A.Vyvod();
}

Текст этой программы можно взять здесь.

Очевидно, что сложность алгоритма есть O(n³). В монографии [2, с.132] отмечено, что "для общего случая (т.е. без предположения о неотрицательности весов или о бесконтурности графа) не известен ни один алгоритм нахождения расстояния между одной фиксированной парой вершин, который был бы значительно эффективнее алгоритма нахождения расстояний между всеми парами вершин."

Замечание. Авторами приведенного алгоритма являются Уоршалл и Флойд (Floyd R.W.).

⁽¹⁾ Трамбле Ж., Соренсон П. Введение в структуры данных. - М.: Машиностроение, 1982. - 784 с.
⁽²⁾ Липский В. Комбинаторика для программистов: Пер. с польск. - М.: Мир, 1988. - 213 с.

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

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