Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

Содержание:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кратчайший путь между не проходит через вершину k, тогда
Существует более короткий путь между , проходящий через 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])

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

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

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

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

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;

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

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

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

Var

Q,W: Real;

K: Char;

X1,X2,Y1,Y2,

X: Integer;

Begin

Open_Graph; {Подключение графического режима}

Q:=2*Pi/N; {Установка значения угла между границами сектора}

{Задание координат вершин графа}

For I:=1 To N Do

Begin

W:=I*Q; {Установка текущего угла}

{Установка координат}

X1:=300+Trunc(R*cos(W)); Y1:=235+Trunc(R*sin(W));

X2:=300+Trunc((R+25)*cos(W)); Y2:=235+Trunc((R+25)*sin(W));

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

K:=Chr(64+I); {Задание текущего названия вершины}

SetColor(White); {Задание цвета названий вершин}

OutTextXY(X2,Y2,K); {Вывод названия вершины}

SetColor(Green); {Задание цвета вершины}

For J:=1 To 7 Do

Circle(X1,Y1,J) {Вывод концентрических окружностей для задания вершины на экране}

End;

{Вывод кратчайшего пути}

X:=Nac;

W:=Q*Nac; {Установка текущего угла}

{Установка координат}

X1:=300+Trunc(R*cos(W)); Y1:=235+Trunc(R*sin(W));

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

SetColor(Red);

PutPixel(X1,Y1,Red);

Repeat

X:=H[X,Kon]; {Переход на следующую вершину в пути}

W:=Q*X; {Установка текущего угла}

{Установка координат}

X2:=300+Trunc(R*cos(W)); Y2:=235+Trunc(R*sin(W));

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

Line(X1,Y1,X2,Y2);

X1:=X2;

Y1:=Y2

Until X=Kon;

SetColor(White);

OutTextXY(3,450,'Press any key, please...');

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

Close_Graph; {Отключение графического режима}

Clrscr

End;

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

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

Begin

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

{Основной блок программы}

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

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

TextBackGround(Black); {Задание цвета фона}

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

Clrscr;

Dlina; {Задание длин дуг}

Floid; {Поиск кратчайшего пути и его длины}

Koordinata {Вывод найденных значений}

End.

Примеры выполнения программы.

Количество вершин 5.

Рис.7. Пример построения графа.

Получение матрицы длин дуг:

Рис. 8. Матрица длин дуг, количество вершин-5.

Рис. 9. Матрица путей, количество вершин-5.

Рис. 10. Матрица длин путей, количество вершин-5.

Рис. 11. Ввод начальной и конечной вершины, количество вершин-5.

Рис. 12. Построение пути между вершинами графа, количество вершин-5.

2. Количество вершин 10.

Рис. 13. Матрица длин дуг, количество вершин-10.

Рис. 14. Матрица путей, количество вершин-10.

Рис. 15. Матрица длин путей, количество вершин-10.

Рис. 16. Ввод начальной и конечной вершины, количество вершин-10.

Рис. 17. Построение пути между вершинами графа, количество вершин-10.

Количество вершин 19.

Рис. 18. Матрица длин дуг, количество вершин-19.

Рис. 19. Матрица путей, количество вершин-19.

Рис. 20. Матрица длин путей, количество вершин-19.

Рис. 21. Ввод начальной и конечной вершины, количество вершин-19.

Рис. 22. Построение пути между вершинами графа, количество вершин-19.

5. Литература:

http://forum.sources.ru/index.php?s=0d1134f14062f7b5d8dccdd6a3a0d731&showtopic=255614
http://80.250.162.180/2011/Alexandra.Shesterneva/graf.doc