![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
Пользователь
Регистрация: 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. |
![]() |
![]() |
![]() |
Опции темы | Поиск в этой теме |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Нахождение кратчайшего пути на графе. | Мария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 |