Шпоры по МПиПА / Графы / Поиск кратчайшего пути методом фронта волны / Pascal / Исходник / waveAlgorithm

Program wave_algorithm;

const max = 100;
type myVector = array[0..max-1] of integer;
type myMatrix = array[0..max-1, 0..max-1] of integer;

var matrixOfSmejnost : myMatrix;
i, j : integer;
fromNode, toNode, dimension : integer;
way : myVector;

function waveAlgorithm( fromNode, toNode, dimension : integer; concatenationMatrix : myMatrix ) : myVector;
var fronts : myMatrix; // Для хранения фронта волны
i, j, k, step : integer;
way, alreadyMarked : myVector; // Для хранения найденного пути и уже однажды пройденных вершин
find : boolean;
begin
for i := 0 to dimension - 1 do // инициализация переменных
for j := 0 to dimension - 1 do
fronts[i,j] := -1;
for i := 0 to dimension do begin
alreadyMarked[i] := 0;
way[i] := -1;
end;

fronts[0,0] := fromNode; // конец инициализации переменнных
step := 0; find := false;

// ищем путь - существует ли он вообще и попутно заполняем матрицу фронтов волны
while ( step < dimension ) and ( not find ) do begin
i := 0;
k := 0;
if fronts[step,0] = -1 then break; // если на предыдущем шаге не найдено ни одной новой вершины - выход

while fronts[step, i] > -1 do begin // поиск всех вершин, в которые можно попасть из текущего фронта
for j := 0 to dimension - 1 do begin
if ( concatenationMatrix[ fronts[step,i], j ] > 0 ) and ( alreadyMarked[j] = 0 ) then begin
alreadyMarked[j] := 1;
fronts[step+1,k] := j;
k := k + 1;
end;
end;
i := i + 1;
end;

i := 0; // определяем нашли ли мы вершину
while fronts[step + 1, i] > -1 do begin
if fronts[step + 1, i] = toNode then begin
find := true;
break;
end;
i := i + 1;
end;

step := step + 1;
end;

if find then begin // если путь найден - ищем маршрут
way[step] := toNode;
for i := step - 1 downto 0 do begin
for k := 0 to dimension - 1 do begin
if concatenationMatrix[fronts[i, k], way[i+1]] > 0 then begin
way[i] := fronts[i, k];
break;
end;
end;
end;
end;

waveAlgorithm := way;
end;

begin
writeln('Wave algoritm.');
write('Enter graph dimension: '); readln( dimension );
for i := 0 to dimension-1 do begin
write('Enter '); write( i + 1 ); write(' row: ');
for j := 0 to dimension-1 do begin
read(matrixOfSmejnost[i,j]);
end;
end;
readln;
write('Enter From Node: '); readln( fromNode );
write('Enter To Node: '); readln( toNode );
write('Question: Exist way from '); write( fromNode ); write(' to '); write( toNode ); writeln('?');
way := waveAlgorithm( fromNode - 1, toNode - 1, dimension, matrixOfSmejnost );
write('Answer: way from '); write( fromNode ); write(' to '); write( toNode ); write(' ');
if ( way[0] = -1 ) then begin
write('not found.');
end
else begin
i := 0;
while ( way[i] <> -1 ) and ( i <= dimension ) do begin
if i <> 0 then write(' -> ');
write( way[i] + 1 );
i := i + 1;
end;
end;
writeln;
writeln('Press Enter to continue...');
readln;
end.