Программа поиска минимального пути в графе между заданными вершинами

Используя поиск в глубину можно найти длину минимального пути в графе между заданными вершинами. Программа решающая данную задачу представлена ниже.

uses crt;

var a:array[1..200,1..200] of byte;

bil:array[1..200] of boolean;

put,d:array[1..300] of integer;

i,n,j,p,na,kon,dl,odl,kz:integer;

f:text;

procedure enter;

begin

assign(f,'input.txt');

reset(f);

read(f,n);

for i:=1 to n do

begin

for j:=1 to n do

read(f,a[i,j]);

end;

close(f);

end;

procedure print;

begin

for i:=1 to n do

begin

for j:=1 to n do

write(a[i,j],' ');

writeln;

end;

end;

procedure poisk(ng,kg,c:integer);

var ii:integer;

begin

if ng=kg then begin

write('Путь:'); dl:=odl;

for ii:=1 to c-1 do

begin

d[ii]:=put[ii];

kz:=c-1;

write(put[ii],' ');

end;

writeln('dl=',dl)

end

else begin

for ii:=1 to n do

if (a[ng,ii]<>0) and (bil[ii]<>true)

and((dl=0)or(odl+a[ng,ii]<dl))

then begin

put[c]:=ii;

bil[ii]:=true;

odl:=odl+a[ng,ii];

poisk(ii,kg,c+1);

put[c]:=0;

bil[ii]:=false;

odl:=odl-a[ng,ii];

end;

end;

end;

procedure enterparam;

begin

write('введите начальную и конечную вершины');

readln(na,kon);

fillchar(bil,sizeof(bil),false);

put[1]:=na;

bil[na]:=true;

p:=1; dl:=0;

poisk(na,kon,p+1);

end;

begin

clrscr;

enter;

print;

enterparam;

write('Путь:');

for i:=1 to kz do

write(d[i],' ');

writeln('длина равна ',dl);

readkey;

end.

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

Литература

1. Ахо Альфред В., Хопкрофт Джон, Ульман Джеффри Д. Структуры данных и алгоритмы.: Пер. с англ.: Уч. пос. — М.: Издательский дом "Вильяме", 2000. — 384 с.: ил. — Парал. тит. англ. (gen.lib.rus.ec)

2. Т.А. Андреева Программирование на языке Pascal

(http://www.intuit.ru/department/pl/plpascal/)

[1] от adjacency – смежность

[2] Поиск в глубину в чистом виде может быть использован, например, для построения дерева подкаталогов. Встаём на корневой каталог, выбираем первый попавшийся подкаталог, далее выбираем в нём какой-либо подкаталог и т.д. пока не доберёмся до пустого (в смысле подкаталогов) каталога. Тогда откатываемся на родительский каталог и выбираем в нём следующий подкаталог, продолжая в нём описанные действия. Как только в каком-либо каталоге просмотрены все подкаталоги, снова откатываемся назад на родительский. К моменту, когда нам придётся откатываться из корневого каталога, мы побываем во всех подкаталогах.

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

Представим теперь, что рёбра графа есть коридоры лабиринта, а вершины - комнаты, соединённые этими коридорами. Мы попадаем в начальную комнату, мы умеем помечать комнаты и нам нужно обойти их все. Пометим нашу комнату и будем делать следующее: выбираем первый попавшийся коридор и ходим по нему; если мы попадаем в помеченную комнату, возвращаемся и выбираем следующий по часовой стрелке коридор (пройдя по всем коридорам комнаты, возвращаемся из неё по коридору, по которому в неё пришли), а если нет, то помечаем новую комнату и продолжаем выбирать коридоры указанным способом. Когда мы пройдем по всем коридорам из начальной комнаты, мы точно побываем в каждой комнате лабиринта.

[3] или другое объяснение:

· находясь в вершине x, нужно двигаться в любую другую, ранее не посещенную вершину (если таковая найдется), одновременно запоминая дугу, по которой впервые попали в данную вершину;

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

[4] Если мы представим, что рёбра есть трубы с одинаковой шириной, то подобное "расползание" очень напоминает распространение воды по трубам если начать эту самую воду равномерно заливать в начальную вершину.

[5] http://comp-science.narod.ru/KPG/Deikstr.htm

В.С. Князьков, Т.В. Волченская Введение в теорию графов http://www.intuit.ru/department/algorithms/ingrth/9/3.html

Дата добавления: 2015-10-13