Графы. Алгоритм Флойда — Уоршелла

     Содержание:

1. Графы. Основные определения с примерами…………………………………..2
2. Алгоритм Флойда — Уоршелла…………………………………………………..4
3. Листинг программы………………………………………………………………..5
4. Примеры выполнения программы……………………………………………..12
5. Литература…………………………………………………………………………17

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
     

1. Графы. Основные определения  с примерами.

     Граф – это некоторое конечное множество точек, называемых вершинами, и конечный набор линий, называемых ребрами, соединяющих некоторые пары точек и .

      Пример 1: схема автомобильных дорог, связывающих города некоторой области, является характерным примером графа.

       
 

     Рис.1. Пример 1.

     Ориентированный граф (орграф) – это граф, у которого пары в наборе X являются упорядоченными.

     Пример 2: пусть ,  .

     Тогда – ориентированный граф.

     Дуга – это направленное ребро в орграфе.

     Пример 3: в приведенном выше примере для орграфа дугами являются ребра , , _.

     Начальная вершина – вершина орграфа, которой инцидентны только исходящие дуги.

      Пример 4: пусть – ориентированный граф, , , тогда – начальная вершина. 
 
 

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

     Конечная  вершина – вершина орграфа, которой инцидентны только заходящие дуги.

      Пример 5: пусть – ориентированный граф, , , тогда – конечная вершина. 
 
 

                    Рис.3. Пример 5.

     Петля – ребро графа, инцидентное единственной вершине.

     Пример 6: пусть – ориентированный граф, ,

      , тогда  , , – петли. 
 
 

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

     Изолированная вершина – вершина, которая не имеет инцидентных ребер.

     Пример 7: пусть – ориентированный граф, , , тогда , – изолированные вершины.

       
 

                 Рис.5. Пример 7.  

     Степень вершины – число инцидентных ребер, .

     Пример 8: пусть – граф, изображенный на рисунке. Тогда , , – соответственно степени вершин , , .

       

      

     Рис.6. Пример 8. 

2. Алгоритм Флойда — Уоршелла

     Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. 

     Пусть вершины графа   пронумерованы от 1 до n и введено обозначение   для длины кратчайшего пути от i до j, который кроме самих вершин   проходит только через вершины  . Очевидно, что   — длина (вес) ребра  , если таковое существует (в противном случае его длина может быть обозначена как  )

     Существует  два варианта значения  :

1. Кратчайший путь между   не проходит через вершину k, тогда 
2. Существует более короткий путь между  , проходящий через k, тогда он сначала идёт от i до k, а потом от k до j. В этом случае, очевидно, 

     Таким образом, для нахождения значения функции  достаточно выбрать минимум из двух обозначенных значений.

     Тогда рекуррентная формула для   имеет вид:

       — длина ребра 

     

     Алгоритм  Флойда — Уоршелла последовательно вычисляет все значения  ,   для k от 1 до n. Полученные значения   являются длинами кратчайших путей между вершинами  .

     Псевдокод

     На  каждом шаге алгоритм генерирует двумерную матрицу W,  . Матрица W содержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрица W заполняется длинами рёбер графа.

     for k = 1 to n

       for i = 1 to n

         for j = 1 to n

           W[i][j] = min(W[i][j], W[i][k] + W[k][j])

     Сложность алгоритма

     Три вложенных цикла содержат операцию, исполняемую за константное время.   то есть алгоритм имеет кубическую сложность, при этом простым расширением можно получить также информацию о кратчайших путях — помимо расстояния между двумя узлами записывать в матрицу идентификатор первого узла в пути.

3. Листинг программы:

     Program Algoritm_Floid;

     {Программа  поиска кратчайшего пути между  вершинами и его длины при

     помощи  алгоритма Флойда}

     Uses Crt,Graph,Graphs;

     Const

 

   M=19; {Предельное  число вершин графа}

 

   R=200; {Радиус  окружности на которой лежат вершины (центры окружностей)}

     Type

 

   Dmas = Array[1..M,1..M] Of Integer;

     Var

 

   N,            {Число вершин графа}

 

   I,J,

 

   Nac,          {Номер начальной вершины}

 

   Kon: Integer; {Номер конечной вершины}

 

   T,            {Матрица, хранящая длины путей}

 

   H,            {Матрица, хранящая пути}

 

   C: Dmas;      {Матрица, хранящая длины дуг}

     {===========================================================================}

     {                       Процедуры используемые в программе                  }

     {===========================================================================}

 

 Procedure Dlina;

 

 {----------------------------------}

 

 {Процедура задания  матрицы длин дуг}

 

 {----------------------------------}

 

 Begin

 

 GotoXY(7,7);

 

 Write('Введите число вершин графа: ');

 

 Readln(N); {Задание значения числа вершин}

 

 If N>M Then Halt; {Если вершин больше чем константа M, то выход из программы}

 

 Clrscr; {Очистка экрана}

 

  If N>5 Then  {Автоматическое задание значений длин дуг}

 

    For I:=1 To N Do

 

      For J:=1 To N Do

 

      If I=J Then C[I,J]:=0

 

        Else C[I,J]:=Random(100)+1 {Генерация текущего значения}

 

    Else

 

     Begin    {Задание длин дуг вводом с клавиатуры}

 

       For I:=1 To N Do

 

         Begin

 

          Writeln;

 

          For J:=1 To N Do

 

           If I<>J Then

 

             Begin

 

               Write('Введите вес дуги [',I,',',J,']:= ');

 

               Readln(C[I,J]) {Ввод с клавиатуры значения длины дуги}

 

             End

 

           Else If I=J Then C[I,J]:=0;

 

          End

 

       End;

 

  {Вывод полученной  матрицы дуг}

 

  Clrscr; {Очистка экрана}

 

  Writeln('Матрица длин дуг');

 

  Writeln;

 

  Write('   ');

 

  TextColor(Green); {Задание цвета текста}

 

  For I:=1 To N Do

 

    Write('  ',Chr(64+I),' ');

 

  Writeln;

 

  For I:=1 To N Do

 

    Begin

 

      TextColor(Green); {Задание цвета текста}

 

      Write(' ',Chr(64+I),' ');

 

      TextColor(White); {Задание цвета текста}

 

     For J:=1 To N Do

 

       Write(C[I,J]:3,' '); {Вывод текущего элемента матрицы}

 

      Writeln

 

    End;

 

  Readln {Задержка экрана}

 

  End;

 

  {---------------------------------------------------------------------}

 

  Procedure Floid;

 

  {-----------------------------------------------}

 

  {Процедура нахождения  кратчайших путей и их длин}

 

  {-----------------------------------------------}

 

  Var

 

     I,J,K: Integer;

 

  Begin

 

    For I:=1 To N Do

 

      For J:=1 To N Do

 

       Begin

 

         T[I,J]:=C[I,J]; {Начальная установка длин путей}

 

         If C[I,J]=100 Then

 

            H[I,J]:=0 {Нет дуги из вершины "I" в "J" вершину}

 

         Else

 

            H[I,J]:=J {Есть дуга из вершины "I" в "J" вершину}

 

       End;

 

    For I:=1 To N Do

 

     Begin

 

      For J:=1 To N Do

 

        For K:=1 To N Do

 

        If (I<>J) And (T[J,I]<>0) And (I<>K) And (T[I,K]<>0)

       and ((T[J,K]=0) Or (T[J,K]>T[J,I]+T[I,K])) Then            

 

             Begin

 

               H[J,K]:=I; {Запоминаем новый путь}

 

               T[J,K]:=T[J,I]+T[I,K] {Запоминаем длину данного нового пути}

 

             End;

 

      For J:=1 To N Do

 

        for k:=1 to n do

       If j=k Then t[j,k]:=0{Нет решения: вершина входит в цикл отрицательной длины}

 

     End;

 

  {Вывод полученной  матрицы путей}

 

  Clrscr; {Очистка экрана}

 

  Writeln('Матрица путей');

 

  Writeln;

 

  Write('   ');

 

  TextColor(Green); {Задание цвета текста}

 

  For I:=1 To N Do

 

    Write('  ',Chr(64+I),' ');

 

  Writeln;

 

  For I:=1 To N Do

 

    Begin

 

      TextColor(Green); {Задание цвета текста}

 

      Write(' ',Chr(64+I),' ');

 

      TextColor(White); {Задание цвета текста}

 

     For J:=1 To N Do

 

       Write(H[I,J]:3,' '); {Вывод текущего элемента матрицы}