Выполнение поставленой Задачи

Ручной просчет.

Даны 3 ориентированных графа G1(5,12), G2(4,7), G3(7,14), заданные матрицами смежности. Построить для этих графов деревья кратчайших путей.

Матрица смежности графа G1:

0 6 7 7 2

0 0 3 8 -3

0 -1 0 0 -4

0 0 -3 0 9

0 0 7 0 0

Массив предков:

ftr = (0, 3, 4, 1, 3).

Массив расстояний от 1-ой

начальной вершины до остальных:

l = (0, 3, 4, 7, 0).

Матрица смежности графа G2:

0 7 0 5

4 0 3 -1

-2 0 0 -6

0 0 0 0

Массив предков:

ftr = (0, 1, 2, 3).

Массив расстояний от 1-ой

начальной вершины до остальных: Рис. 5: Граф G2. 10

l = (0, 7, 10, 4).

Матрица смежности графа G3:

0 5 0 0 1 0 3

0 0 4 0 7 0 0

0 -4 0 0 -3 0 0

0 0 2 0 0 8 0

0 0 0 2 0 3 0

3 0 0 4 0 0 0

0 0 0 0 0 -1 0

Массив предков:

ftr = (0, 3, 4, 5, 1, 7, 1).

Массив расстояний от 1-ой

начальной вершины до остальных:

l=(0,1, 5, 3, 1, 2, 1).

Тест программы.

В графе G2 есть вершина, из которой нельзя построить дерево кратчайших путей – это 4 вершина, так как из неё не выходят дуги. Программа проводит проверку на заданную пользователем вершину, в нашем случае 4, и проводит проверку и обнаруживает, что 4 не подходит. Далее программа вновь предлагает ввести номер вершины и для введенной 2 успешно вычисляет выходные массивы. Правильность данных можно проверить, сверив их с деревом кратчайших путей для графа G2 с начальной 2 вершиной на рисунке 13.

КОД ПРОГРАММЫ.

program kurs;

uses crt;

const m=10;

type matrix= array [1..m, 1..m] of integer;

massiv= array [1..m] of integer;

var i,j,min,c,k,s,n: integer;

v,l,ftr: massiv;

smej: matrix;

f: file of integer;

label metka;

procedure vvod1(n: integer; var smej: matrix);

begin

assign(f,'data/graph_1.bin');

reset(f);

for i:=1 to n do

for j:=1 to n do

begin

read(f,c);

smej[i,j]:=c;

end;

close(f);

end;

procedure vvod2(n: integer; var smej: matrix);

begin

assign(f,'data/graph_2.bin');

reset(f);

for i:=1 to n do

for j:=1 to n do

begin

read(f,c);

smej[i,j]:=c;

end;

close(f);

end;

procedure vvod3(n: integer; var smej: matrix);

begin

assign(f,'data/graph_3.bin');

reset(f);

for i:=1 to n do

for j:=1 to n do

begin

read(f,c);

smej[i,j]:=c;

end;

close(f);

end;

Begin clrscr;

write('Введите число вершин исследуемого графа (4,5,7) '); 14 read(n);

case n of

5: vvod1(n,smej);

4: vvod2(n,smej);

7: vvod3(n,smej);

end;

write('Ведите исходную вершину ');

metka: read(i);

s:=0;

for k:=1 to n do

if not(smej[i,k]=0) then s:=1;

if s=0 then

begin

writeln('Из этой вершины нет выходящих дуг.');

write('Bведите другую вершину ');

goto metka

end;

writeln('Матрица смежности: ');

for k:=1 to n do begin

for s:=1 to n do

if smej[k,s]<0 then

write(' ',smej[k,s])

else

write(' ',smej[k,s]);

writeln;

end;

for j:=1 to n do begin

l[j]:=smej[i,j];

ftr[j]:=i;

if l[j]=0 then l[j]:=99;

end;

l[i]:=0;

for j:=1 to n do begin

min:=l[j];

for k:=1 to n do

if not(smej[k,j]=0) and not(k=i) then

if smej[k,j]<min then

begin

c:= k;

min:=smej[k,j];

end;

v[j]:= l[c]+smej[c,j];

if v[j]<l[j] then

begin

l[j]:=v[j];

ftr[j]:=c;

j:=1;

end;

End;

ftr[i]:=0; l[i]:=0;

writeln('Массив предков: ');

write(' ftr =');

for k:= 1 to n do

write(' ',ftr[k]);

writeln;

writeln('Массив со значениями кратчайших путей от ',i,' вершины: ');

write(' l =');

for k:=1 to n do

if l[k]<0 then

write(' ',l[k])

else

write(' ',l[k]);

End.

ПРИЛОЖЕНИЕ.

Коды программ используемые для создания файлов с данными.

Для 1-го графа.

program graph1;

uses crt;

const n=5;

type matrix= array [1..n, 1..n] of integer;

var i,j,c,n: integer;

smej: matrix;

f: file of integer;

Begin clrscr;

smej[1,2]:=6; smej[1,3]:=7; smej[1,4]:=7; smej[1,5]:=2;

smej[2,3]:=3; smej[2,4]:=8; smej[2,5]:=-3;

smej[3,2]:=-1; smej[3,5]:=-4;

smej[4,3]:=-3; smej[4,5]:=9;

smej[5,3]:=7;

assign(f,'data/graph_1.bin');

rewrite(f);

for i:=1 to n do

for j:=1 to n do

begin

c:=smej[i,j];

write(f,c);

end;

close(f);

End.

Для 2-го графа.

program graph2;

uses crt;

const n=4;

type matrix= array [1..n, 1..n] of integer;

var i,j,c,n: integer;

smej: matrix;

f: file of integer;

Begin clrscr;

smej[1,2]:=7; smej[1,4]:=5;

smej[2,1]:=4;smej[2,3]:=3; smej[2,4]:=-1;

smej[3,1]:=-2; smej[3,4]:=-6;

assign(f,'data/graph_2.bin');

rewrite(f);

for i:=1 to n do

for j:=1 to n do

begin

c:=smej[i,j];

write(f,c);

end;

close(f);

End.

Для 3-го графа.

program kurs;

uses crt;

const n=7;

type matrix= array [1..n, 1..n] of integer;

var i,j,c,n: integer;

smej: matrix;

f: file of integer;

Begin clrscr;

smej[1,2]:=5; smej[1,5]:=1; smej[1,7]:=3;

smej[2,3]:=4; smej[2,5]:=7;

smej[3,2]:=-4; smej[3,5]:=-3;

smej[4,3]:=2; smej[4,6]:=8;

smej[5,4]:=2; smej[5,6]:=3;

smej[6,1]:=3; smej[6,4]:=4;

smej[7,6]:=-1;

assign(f,'data/graph_3.bin');

rewrite(f);

for i:=1 to n do

for j:=1 to n do

begin

c:=smej[i,j];

write(f,c);

end;

close(f);

End.

СПИСОК ЛИТЕРАТУРЫ.

1. В.Н. Землянухин, Л.Н. Землянухина – Задачи оптимизации на графах. 2009г.

2. А.Е. Костин, В.Ф. Шаньгин – Организация и обработка структур данных в 3. вычислительных системах. Учебное пособие для вузов. 1987г.

4. Ж. Трамбле, П. Соренсон – Введение в структуры данных. 1982г.

5. Ф. Харари – Теория графов. 1973г.

6. В. Липский – Комбинаторика для программистов. 1988г.

7. В.Л. Бурковский, Л.В. Холопкина, Н.Л. Райхель, О.Я. Кравец – Методы моделирования и анализа вычислительных систем. Учебное пособие. 1996г.

8. В.А. Евстигнеев, В.Н. Касьянов – Графы в программировании: обработка, визуализация и применение.