Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 30.11.2012, 18:22   #1
zokwild
Пользователь
 
Регистрация: 17.11.2011
Сообщений: 11
По умолчанию поиск кратчайшего пути в графе

программа должна искать кратчайший путь между двумя вершинами графа.Не могу найти ошибку.Подскажите где?
Program wave_algorithm;

cоnst 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 := 0;
way := -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 := 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 <> -1 ) and ( i <= dimension ) do begin
if i <> 0 then write(' -> ');
write( way + 1 );
i := i + 1;
end;
end;
writeln;
writeln('Press Enter to continue...');
readln;
end.
zokwild вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нахождение кратчайшего пути на графе. Мария74 Помощь студентам 14 31.10.2012 21:36
Поиск кратчайшего пути в графе BaceK Помощь студентам 0 18.12.2011 11:49
Поиск кратчайшего пути в графе методом полного перебора в глубину. Метод ветвей и границ Олинька Помощь студентам 1 24.12.2008 16:22
1) Поиск кратчайшего пути в графе методом полного перебора в ширину(очередь) Serega123 Помощь студентам 3 30.10.2008 22:26