Алгоритмынахождениякратчайшихпутейвграфе (стр. 2 из 2)
Рис. 13: Дерево кратчайших путей для графа G2 с начальной вершиной №2.
КОД ПРОГРАММЫ.
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) '); 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.
СПИСОК ЛИТЕРАТУРЫ.
В.Н. Землянухин, Л.Н. Землянухина – Задачи оптимизации на графах. 2009г.
А.Е. Костин, В.Ф. Шаньгин – Организация и обработка структур данных в вычислительных системах. Учебное пособие для вузов. 1987г.
Ж. Трамбле, П. Соренсон – Введение в структуры данных. 1982г.
Ф. Харари – Теория графов. 1973г.
В. Липский – Комбинаторика для программистов. 1988г.
В.Л. Бурковский, Л.В. Холопкина, Н.Л. Райхель, О.Я. Кравец – Методы моделирования и анализа вычислительных систем. Учебное пособие. 1996г.
В.А. Евстигнеев, В.Н. Касьянов – Графы в программировании: обработка, визуализация и применение.