Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Исследование свойств графа - файл 1.doc


Исследование свойств графа
скачать (29 kb.)

Доступные файлы (1):

1.doc29kb.18.12.2011 17:37скачать


1.doc

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(Государственный Технический Университет)

филиал «Восход»

Кафедра ВТ



Отчет


по лабораторной работе №2

на тему «Исследование свойств графа»

по дисциплине: дискретная математика


Выполнил студент группы ДМ2-27 Князева М.А.________


«____»__________200__г.

Проверил преподаватель Крохина Н.В._________________

«____»__________200__г.
Байконур 2004г.

Цель работы: Смоделировать процедуру нахождения максимального дерева кратчайших расстояний.
Листинг программы
program laba2;

const n=5;

m=100;

var x,p,e:integer;

a:array[1..n,1..n] of integer;

f,t,g:array[1..n] of integer;

procedure zadan;

{процедура задания матрицы смежности взвешенного графа}

var i,j:integer;

begin

for i:=1 to n do

for j:=1 to n do a[i,j]:=m;

for i:=1 to n do a[i,i]:=0;

{присваивание рёбрам графа весов} a[1,2]:=11;

a[1,3]:=15;a[1,4]:=9; a[2,1]:=11;a[2,3]:=3;a[2,5]:=8;

a[3,1]:=15;a[3,2]:=3; a[3,4]:=5; a[3,5]:=2;a[4,1]:=9;

a[4,3]:=5; a[4,5]:=13;a[5,2]:=8; a[5,3]:=2;a[5,4]:=13;

end;

procedure raspech;

{вывод матрицы}

var i,j:integer;

begin

writeln;

writeln('Матрица смежности взвешенного графа');writeln;

writeln(' 1 2 3 4 5');

writeln(' -------------------');

for i:=1 to n do begin

write;for j:=1 to n do

if a[i,j]=m then begin

if j=1 then case i of

1: write('1 |'); 2: write('2 |'); 3: write('3 |');

4: write('4 |'); 5: write('5 |'); end;

write(' - |') end

else begin

if j=1 then case i of

1: write('1 |'); 2: write('2 |'); 3: write('3 |');

4: write('4 |'); 5: write('5 |'); end;

write(a[i,j]:3,'|'); end;

writeln; end;

writeln(' -------------------'); writeln;

end;

{***дерево кратчайших путей***}

procedure krat_put;

label 1;

var d,u,v: array[1..n] of integer;

s,m,i,j,k,l,jk:integer;

begin

e:=0; s:=x; m:=n-1;

for i:=1 to n do begin

u[i]:=i; d[i]:=a[x,i]; v[i]:=x; end;

u[x]:=n; d[x]:=d[n]; goto 1;

repeat

d[k]:=d[m]; u[k]:=u[m]; v[k]:=v[m]; dec(m);

{обновление кратчайшего расстояния}

for i:=1 to m do begin

j:=u[i]; jk:=l+a[s,j];

if d[i]>jk then begin

v[i]:=s; d[i]:=jk; end; end;

1:{запоминание кратчайшего расстояния}

k:=1; l:=d[1];

for i:=1 to m do if d[i]<l then begin

l:=d[i]; k:=i end;

{добавление вершин к дереву кратчайших расстояний}

inc(e); f[e]:=v[k]; t[e]:=u[k]; g[e]:=l; s:=u[k];

until s=p; {достигнута ли вершина p}

end;

procedure put;

var i:integer;

begin

writeln;

writeln('кратчайшее расстояние между узлами ',x,' и ',p,' равно ',g[e]);

end;

{основной блок}

Begin

zadan; raspech;

x:=1; p:=5;

krat_put; put; readln;

end.

Результат



Матрица смежности взвешенного графа

1 2 3 4 5

--------------------------

1 | 0 | 11 | 15 | 9 | - |

2 | 11 | 0 | 3 | - | 8 |

3 | 15 | 3 | 0 | 5 | 2 |

4 | 9 | - | 5 | 0 | 13 |

5 | - | 8 | 2 | 13 | 0 |

--------------------------

кратчайшее расстояние между узлами 1 и 5 равно 16


Скачать файл (29 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации