СКАЧАТЬ: zadacha1.zip [146,03 Kb] (cкачиваний: 24)

Министерство образования и науки РТ

Aльметьевский государственный нефтяной институт

Кафедра АИТ

    Задача №1

по дисциплине

«Моделирование систем»

на тему:

«Алгоритм Флойда-Уоршелля»

Построение математической модели

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

Постановка задачи: пусть дан непустой взвешенный граф G=(V, E) с произвольными весами ребер (дуг). Требуется найти длины кратчайших путей между всеми парами вершин графа

 Применительно к прикладной задаче целью разработки приложения является – определение наиболее эффективного маршрута пересылки сообщений между любыми двумя районами. Причем алгоритм может решать подобные задачи для разных критериев, например, критерием может быть – поиск наиболее дешевого пути (каждой дуге ставится в соответствие денежный эквивалент, который необходимо затратить при использовании этой дуги); или поиск наиболее быстрого пути (в этом случае каждой дуге присваивается время, которое будет потрачено при ее использовании); можно таким же образом найти самый надежный путь (каждой дуге ставится в соответствие коэффициент риска передачи сообщения по этой дуге/пути). Подобных задач может возникнуть очень много, а цель этих задач одинакова – нахождение кратчайшего пути из одного состояния в другое (относительно графа – нахождение минимального расстояния между 2-мя вершинами).

Описание математического метода

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

Схема 2. Треугольный оператор

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

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

Схема 3.Первоначальная ситуация

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

Схема 4. Иллюстрация алгоритма Флойда

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

Расстояние между узлами i и j равно элементу d_ij в матрице D_n.

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

Схема 5. Треугольный оператор

Расчет математической модели

Составим для поставленной задачи изображенной на рисунке 1 матрицу смежности, получим матрицу D₀ схема 6.

Схема 6. Первоначальная матрица

Применим к ней алгоритм Флойда, получим следующую матрицу кратчайших путей и матрицу маршрутов схема 7:

Схема 7. Результат работы алгоритма

Таким образом, например, кратчайшее расстояние из первой вершины во вторую равно 4. Из шестой в седьмую равно 9, причем проходим через 5-ю вершину, из пятой в первую расстояние равно 10, и проходим через 7-ю вершину, схема 8.

Схема 8. Результат работы алгоритма показан на графе

Путь из 6 в 9 равен 2+7=9.Путь из 1 в 2 равен 4

Программа поиска кратчайшего пути между вершинами и его длины при  помощи алгоритма Флойда реализованный в среде turbopascal:

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]<>100) And (I<>K) And (T[I,K]<>100)

      And ((T[J,K]=100) 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

      If T[J,J]<0 Then Break {Нет решения: вершина входит в цикл отрицательной длины}

     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,' '); {Вывод текущего элемента матрицы}

      Writeln; End;

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

  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(T[I,J]:3,' '); {Вывод текущего элемента матрицы} Writeln; End;

  Readln;   Clrscr;  GotoXY(10,10);

  Write('Введите номер начальной вершины пути: '); Readln(Nac);

  GotoXY(10,12);

  Write('Введите номер конечной вершины пути: '); Readln(Kon);

  Writeln; Write('Длина пути из вершины ',Chr(64+Nac),' в вершину ',Chr(64+Kon),' равна: ',T[Nac,Kon]);

  Readln    End; Procedure Koordinata;

  {Процедура вывода найденных значений}

End.