Размещено на http://www.allbest.ru/

МИХАЙЛОВСКАЯ ВОЕННАЯ АРТИЛЛЕРИЙСКАЯ АКАДЕМИЯ

Кафедра № 52

Научно-исследовательская работа по дисциплине

Дискретная математика для программистов

Тема: "Нахождение кратчайших путей в графе методом Флойда"

Учебное отделение 631

Выполнил:

курсант Рябчиков С.В.

Научный руководитель: профессор Боев В.Д.

Санкт-Петербург

2009 год.

Оглавление

• 1. Основные понятия и определения теории графов
• 2. Методы нахождения кратчайших путей в графе
• 3. Алгоритм Флойда
• 4. Листинг программы
• 5. Примеры применения программы
• 5. Литература

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

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

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

2. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными.

3. Граф, состоящий только из изолированных вершин, называется нуль-графом(O').

4. Граф, в котором каждая пара вершин соединена

5. ребром, называется полным(U').

6. Степенью вершины называется число ребер, которым принадлежит вершина. Обозначение: p (A) - степень вершины A.

7. Граф, степени всех k вершин которого одинаковы, называется однородным графом степени k.

8. Дополнением данного графа называется граф, состоящий из всех ребер и их концов, которые необходимо добавить к исходному графу, чтобы получить полный граф.

9. Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским.

10. Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью.

11. Путем от A до X называется последовательность ребер, ведущая от A к X, такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.

12. Циклом называется путь, в котором совпадают начальная и конечная точка.

13. Простым циклом называется цикл, не проходящий ни через одну из вершин графа более одного раза.

14. Длиной пути, проложенного на цикле, называется число ребер этого пути.

15. Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B.

16. Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным.

17. Деревом называется связный граф, не содержащий циклов.

18. Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми ребрами (дугами), соединяющими вершины из этого множества. Если из графа удалить часть ребер (дуг), то получим частичный граф.

19. Определим матрицу смежности графа как квадратную матрицу n х n, элемент a_ij которой равен единице, если между вершинами есть связь и нулю, если нет. Для неориентированного графа матрица смежности всегда симметрическая.

20. Определим матрицу инциденций для ребер графа как прямоугольную матрицу n х m, элемент Гц которой равен единице, если вершина i инцидентна ребру j , и нулю в противном случае.

21. Аналогично определяется матрица инциденций для дуг графа - как прямоугольная матрицу m хп, элемент Гц которой равен плюс единице, если дуга Uj исходит из вершины i, минус единице, если дуга Ц заходит в вершину i, и нулю в остальных случаях.

22. Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого - U, содержащий те и только те рёбра, оба конца которых входят в U.

23. Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

24. Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежные.

2. Методы нахождения кратчайших путей в графе

Начальные понятия

Будем рассматривать ориентированные графы G =(V,E) , дугам которых приписаны веса. Это означает, что каждой дуге E поставлено в соответствие некоторое вещественное число a (u, v), называемое весом данной дуги.

Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами s, t ?V. Длину такого кратчайшего пути мы будем обозначать d (s, t) и называть расстоянием от s до t (расстояние, определенное таким образом, может быть отрицательным). Если не существует ни одного пути из s в t, то полагаем d (s, t) = + . Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v1,..., vp не будет повторов.

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

Сначала рассмотрим алгоритмы нахождения расстояния между вершинами, а не самих путей. Однако, зная расстояние, мы можем при условии положительной длины всех контуров легко определить кратчайшие пути. Для этого достаточно отметить, что для произвольных s, t ? V (s , t) существует вершина v, такая что d (s, t) = d (s, v) + a (v, t).

Действительно, таким свойством обладает предпоследняя вершина произвольного кратчайшего пути из s в t.

Далее мы можем найти вершину u, для которой d (s, v) = d (s, u) + a(u, v), и т.д.

Из положительности длины всех контуров легко следует, что созданная таким образом последовательность t, v, u, ... не содержит повторений и оканчивается вершиной s. Очевидно, что она определяет (при обращении очередности) кратчайший путь из s в t.

Способы задания графа

Явное задание графа как алгебраической системы.

Геометрический

Матрица смежности

Матрица инцидентности

Рассмотрим различные способы задания для одного и того же графа.

1. < {а, Ь, с, d), {и, v, w,x); {(и, а),(и, b),(v, b),(v, c),(w, c),(w, a),(x, с), (x, d)} >. Так как мы рассматриваем только простые графы, граф нам проще определять как модель, носителем которой является множество вершин, а отношение - бинарное отношение смежности вершин. Тогда данный граф запишется как<{а,Ь,с,с1}; {(a,b), (b,a),(b,c),(c,b),(a,c),(c,a),(c,d),(d,c)}>. В таком представлении ребру соответствуют две пары вершин (v, ) и (v. ), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин - его мы и будем отождествлять с ребром. Для данного графа рёбра задаются множеством {{a,b},{b,c},{a,c},{c,d}} и граф мы будем записывать как пару (V,E), где V-множество вершин, а Е - множество рёбер.

В дальнейшем мы будем опираться именно на второе определение графа.

2. Геометрический

3. Матрица смежности

	а	b	с	d
а	0	1	1	0
b	1	0	1	0
с	1	1	0	1
d	0	0	1	0

4. Матрица инцидентности

	u	V	w	X
а	1	0	0	0
b	1	1	1	0
с	0	1	0	1
d	0	0	1	1

3. Алгоритм Флойда

Алгоритм Флойда находит кратчайшие пути между всеми парами вершин в орграфе. В этом алгоритме для хранения информации о путях используется матрица H[1..р, 1..р], где

ОТСТУПЛЕНИЕ

Матрица Н размера 0(р²) хранит информацию обо всех (кратчайших) путях в графе. Заметим, что всего в графе 0(р²) путей, состоящих из 0(р) вершин. Таким образом, непосредственное представление всех путей потребовало бы памяти объема 0(р³). Экономия памяти достигается за счет интерпретации представления, то есть динамического вычисления некоторой части информации вместо ее хранения в памяти. В данном случае любой конкретный путь (u>v) легко извлекается из матрицы с помощью следующего алгоритма.

Алгоритм Флойда

ЗАМЕЧАНИЕ

Если в G есть цикл с отрицательным весом, то решения поставленной задачи не существует, так как можно "накручивать" на этом цикле сколь угодно короткий путь.

Обоснование

Алгоритм Флойда имеет много общего с алгоритмом Уоршалла (алгоритм 1.8). Покажем по индукции, что после выполнения i-го шага основного цикла по I элементы матриц T[j,k] и H[j, k] содержат, соответственно, длину кратчайшего пути и первую вершину на кратчайшем пути из вершины j в вершину к, проходящем через промежуточные вершины из диапазона 1..i. База: i = 0, то есть до начала цикла элементы матриц Т и H содержат информацию о кратчайших путях (если таковые есть), не проходящих ни через какие промежуточные вершины. Пусть теперь перед началом выполнения тела цикла на i-м шаге T(j, k) содержит длину кратчайшего пути от j к k , a H\j> к) содержит первую вершину на кратчайшем пути из вершины j в вершину к (если таковой есть). В таком случае, если в результате добавления вершины г к диапазону промежуточных вершин находится более короткий путь (в частности, если это вообще первый найденный путь), то он записывается. Таким образом, после окончания цикла, когда i = p матрицы содержат кратчайшие пути, проходящие через промежуточные вершины 1..р, то есть искомые кратчайшие пути. Алгоритм не всегда выдает решение, поскольку оно не всегда существует. Дополнительный цикл по j служит для прекращения работы в случае обнаружения в графе цикла с отрицательным весом.

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

Примечание: бесконечность в программе вводить и обозначать как "888"

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ComCtrls, Grids, StdCtrls, Menus;

type

TForm1 = class(TForm)

Edit1: TEdit;

Edit2: TEdit;

StringGrid1: TStringGrid;

UpDown1: TUpDown;

UpDown2: TUpDown;

Button1: TButton;

StringGrid2: TStringGrid;

StringGrid3: TStringGrid;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Button2: TButton;

Label4: TLabel;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

Button3: TButton;

Label5: TLabel;

Label6: TLabel;

procedure UpDown1Click(Sender: TObject; Button: TUDBtnType);

procedure UpDown2Click(Sender: TObject; Button: TUDBtnType);

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure N2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

i,j,k:integer;

c,t,h:array[1..20,1..20] of integer;

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var

I: Integer;

begin

for i := 0 to StringGrid1.ColCount - 1 do begin

for j := 0 to StringGrid1.RowCount - 1 do begin

if i=j then

stringgrid1.cells[i,j]:=inttostr(0);

end;//j

end;//i

for i := 0 to StringGrid1.ColCount - 1 do begin

for j := 0 to StringGrid1.RowCount - 1 do begin

if stringgrid1.cells[i,j]='' then begin

label4.visible:=true;

exit;

end;//i

end;//j

end;//i

for i := 0 to StringGrid1.ColCount - 1 do begin

for j := 0 to StringGrid1.RowCount - 1 do begin

c[i,j]:=StrToInt(stringgrid1.cells[i,j]);

end;//j

end;//i

for i := 0 to StringGrid1.ColCount - 1 do begin

for j := 0 to StringGrid1.RowCount - 1 do begin

t[i,j]:=c[i,j];

if c[i,j]=888 then

h[i,j]:=0

else

h[i,j]:=j;

end;//j

end;//i

for i := 0 to StringGrid1.ColCount - 1 do begin

for j := 0 to StringGrid1.RowCount - 1 do begin

for k := 0 to StringGrid1.ColCount - 1 do begin

if (i<>j) and (t[j,i]<>888) and (i<>k) and (t[i,k]<>888) and ((t[j,k]=888) or (t[j,k]>t[j,i]+t[i,k])) then begin

h[j,k]:=h[j,i];

t[j,k]:=t[j,i]+t[i,k];

end;//if

end;//k

end;//j

for j := 0 to StringGrid1.RowCount - 1 do begin

if t[j,j]<0 then break;

end;//j

end;//i

for j := 0 to StringGrid1.ColCount - 1 do begin

for k := 0 to StringGrid1.RowCount - 1 do begin

stringgrid2.cells[j,k]:=inttostr(t[j,k]);

stringgrid3.cells[j,k]:=inttostr(h[j,k]);

end;//k

end;//j

end;

procedure TForm1.Button2Click(Sender: TObject);

begin

for i := 0 to StringGrid1.ColCount - 1 do begin

for j := 0 to StringGrid1.RowCount - 1 do begin

stringgrid1.cells[i,j]:='';

stringgrid2.cells[i,j]:='';

stringgrid3.cells[i,j]:='';

label4.visible:=false;

end;//i

end;//j

end;

procedure TForm1.Button3Click(Sender: TObject);

begin

close;

end;

procedure TForm1.N2Click(Sender: TObject);

begin

close;

end;

procedure TForm1.UpDown1Click(Sender: TObject; Button: TUDBtnType);

begin

StringGrid1.ColCount:=StrToInt(Edit1.text);

StringGrid2.ColCount:=StrToInt(Edit1.text);

StringGrid3.ColCount:=StrToInt(Edit1.text);

end;

procedure TForm1.UpDown2Click(Sender: TObject; Button: TUDBtnType);

begin

StringGrid1.RowCount:=StrToInt(Edit2.text);

StringGrid2.RowCount:=StrToInt(Edit2.text);

StringGrid3.RowCount:=StrToInt(Edit2.text);

end;

end.

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

теория граф алгоритм флойд

Ввод данных

Результаты решения

6. Литература

1. Белов В. В. и др. Теория графов. -- М.: Высшая школа, 1976.

2. Липский В. Комбинаторика для программистов. -- М.: Наука, 1989.

3. Новиков Ф. А. Дискретная математика для программистов. -- СПб.: Питер, 2001.

4. Шапорев С. Д. Дискретная математика. Курс лекций и практических занятий. -- СПб.: БХВ-Петербург, 2006.

Размещено на Allbest.ru