Часть 4. Программирование алгоритма дискретной математики
ЗАДАНИЕ
Запрограммировать алгоритм Флойда отыскания кратчайших путей между всеми парами вершин графа. Алгоритм должен указывать не только длины, но и промежуточные вершины путей по желанию пользователя.
Общие положения. При выполнении задания необходимо
Подробно описать алгоритм.
Подробно описать программу, реализующую алгоритм: типы и структуры данных, блок-схему программы и т.п.
Привести листинг программы.
Привести результаты решения не мене трех тестовых примеров с различными исходными данными.
РЕШЕНИЕ
Описание алгоритма.
Алгоритм Флойда–Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.
Алгоритм:
Пусть
вершины графа 
пронумерованы
от 1 до
и
введено обозначение
для
длины кратчайшего пути отi до j,
который кроме самих вершин 
проходит
только через вершины
.
Очевидно, что
—
длина (вес) ребра
(i,
j) ,
если таковое существует (в противном
случае его длина может быть обозначена
как 
).
Существует
два варианта значения 
:
Кратчайший путь между i, j не проходит через вершину
,
тогда
Существует более короткий путь между i, j проходящий через
,
тогда он сначала идёт от
до
,
а потом от
до
.
В этом случае, очевидно,
Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.
Тогда рекуррентная формула
для 
имеет
вид:
—
длина ребра 
Алгоритм
Флойда–Уоршелла последовательно
вычисляет все значения 
для
от
1 доn.
Полученные значения 
являются
длинами кратчайших путей между вершинамиi,j.
Для реализации алгоритма Флойда, граф будем задавать матрицей инцидентности C(NxN).
Кроме матрицы смежности, воспользуемся еще одной матрицей - WL (NxN), в ней мы будем хранить длины путей из вершины в вершину.
В цикле над матрицей WL (NxN) выполняется n итераций. После k-ой итерации, WL[i,j] содержит значение наименьшей длинны путей из вершины i в вершину j, которые не проходят через вершины с номером, большим k. На k-ой итерации для вычисления матрицы WL, за основу взята следующая формула:
WL k[i,j] = min (WL k-1[i,j], WL k-1[i,k]+ WL k-1[k,j]).
Сложность алгоритма Время выполнения программы, имеет порядок O(n3), так как в ней нет практически ничего, короче 3 вложенных друг в друга циклов. Сохранение маршрутов. Что бы сохранять маршруты, от одной вершины к другой, следует, ввести еще одну матрицу, в которой каждому элементу H[i,j] присваивать вершину K (номер), полученную при нахождении наименьшего значения WL [i,j].
2. Блок схема программы.
рис(4.1)
Основной блок программы
рис 4.2
Процедура определения матрицы длин дуг
рис 4.3
рис 4.4
рис 4.3-4.4 Процедура нахождения кратчайших путей и их длин
рис4.5 Процедура вывода найденных значений
3. Листинг программы.
program alg_floyda;
{$APPTYPE CONSOLE}
uses
SysUtils,
Windows;
Const
M=19; //максимальное число вершин графа
Type
Dmas = Array[1..M,1..M] Of Integer;
Var
FLAG: char;
N, {Число вершин графа}
Nac, {Номер начальной вершины}
Kon: Integer; {Номер конечной вершины}
WL, {Матрица, хранящая длины путей}
H, {Матрица, хранящая пути}
C: Dmas; {Матрица, хранящая длины дуг}
{-------------------------------------------------------}
{ Процедуры и функции используемые в программе }
{-------------------------------------------------------}
{====Функция коррекции вывода====}
function Rus(P1:PAnsiChar):PAnsiChar;
begin
GetMem(Result,Length(P1)+1);
AnsiToOem(P1,Result);
end;
Procedure Dlina;
VAR
I,J:integer;
{====Процедура инициализации матрицы длин дуг====}
Begin
Write (Rus('Введите число вершин графа: '));
Readln(N); //инициализация числа вершин
If N>M Then Halt; //выход из программы, если вершин больше чем M
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(Rus('Введите вес дуги ['),I,Rus(','),J,Rus(']:= '));
Readln(C[I,J]) //ввод с клавиатуры значения длины дуги
End
Else If I=J Then C[I,J]:=0;
End
End;
{Вывод полученной матрицы дуг}
Writeln(Rus('Матрица длин дуг'));
Writeln;
Write(' ');
For I:=1 To N Do
Write(' ',Chr(64+I),' ');
Writeln;
For I:=1 To N Do
Begin
Write(' ',Chr(64+I),' ');
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
WL[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 (WL[J,I]<>100) And (I<>K) And (WL[I,K]<>100)
And ((WL[J,K]=100) Or (WL[J,K]>WL[J,I]+WL[I,K])) Then
Begin
H[J,K]:=I; //запоминаем новый путь
WL[J,K]:=WL[J,I]+WL[I,K] //запоминаем длину данного нового пути
End;
For J:=1 To N Do
If WL[J,J]<0 Then Break //нет решения: вершина входит в цикл отрицательной длины
End;
{Вывод полученной матрицы путей}
Writeln(Rus('Матрица путей'));
Writeln;
Write(' ');
For I:=1 To N Do
Write(' ',Chr(64+I),' ');
Writeln;
For I:=1 To N Do
Begin
Write(' ',Chr(64+I),' ');
For J:=1 To N Do
Write(H[I,J]:3,' '); //вывод текущего элемента матрицы
Writeln
End;
Readln;
{Вывод полученной матрицы длин путей}
Writeln(Rus('Матрица длин путей'));
Writeln;
Write(' ');
For I:=1 To N Do
Write(' ',Chr(64+I),' ');
Writeln;
For I:=1 To N Do
Begin
Write(' ',Chr(64+I),' ');
For J:=1 To N Do
Write(WL[I,J]:3,' '); //вывод текущего элемента матрицы
Writeln;
End;
Readln;
Write(Rus('Введите номер начальной вершины пути: ')); Readln(Nac);
Write(Rus('Введите номер конечной вершины пути: ')); Readln(Kon);
Writeln;
Write(Rus('Длина пути из вершины '),Chr(64+Nac),Rus(' в вершину '),Chr(64+Kon),Rus(' равна: '),WL[Nac,Kon]);
Readln
End;
{====Процедура вывода найденных значений====}
Procedure Koordinata;
Var
X: Integer;
Begin
{Вывод кратчайшего пути}
Writeln;
Write(Rus('Маршрут из вершины '),Chr(64+Nac), Rus(' в вершину '),Chr(64+Kon), Rus(' :'));
Writeln;
Writeln;
X:=Nac;
Write( Chr(64+X));
Repeat
X:=H[X,Kon]; //переход на следующую вершину в пути
Write('->');
Write(Chr(64+X));
Until X=Kon;
Readln;
End;
Begin
{====Основной блок программы====}
Dlina; //задание длин дуг
Floid; //поиск кратчайшего пути и его длины
Writeln;
Write(Rus('Вывести маршрут? (y/n)'));
Read(flag);
if (flag=('y') )then
Koordinata; //вывод найденных значений
Readln;
End.
4.Результаты работы программы
Тестовый набор данных №1
Тестовый набор данных №2
Тестовый набор данных №3
