Помощь - Поиск - Пользователи - Календарь
Полная версия: Программа поиска кратчайшего пути
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Dmitriy
Народ, помогите решить плиз. Имеется N городов. Некоторые из них соединены дорогами известной длины. Система дорог моделируется матрицей N*N , элемент Аi,j равен -1, если соответсвующие I и J города не соединены прямой дорогой, или числу=длине дороги в противном случае. Программа поиска кратчайшего пути между K и L городами.
мисс_граффити
Алгоритм не задан?
У меня есть лабораторка по дискретке, где один из алгоритмов реализуется.
Но не программкой, а просто вручную. Хотя все довольно легко (на первый взгляд, во всяком случае) кодируется. Если хочешь, скинь в личку свое мыло - я отправлю (там doc-файл).
Dmitriy
Алгоритм не задан. Единственное о чем догадываюсь кроме алгоритма так называемой волны - это о том что длины нужно хранить во вспомогательном массиве. Буду весьма признателен за алгоритм.
мисс_граффити
Проверяй мыло. Если что непонятно - спрашивай...
Dmitriy
Цитата(мисс_граффити @ 15.04.2007 13:58) *

Проверяй мыло. Если что непонятно - спрашивай...

спасибо, разобрался, как запрограммирую так и код размещу(надеюсь)
Dmitriy
uses crt;
var w,g,s:array [1..100,1..100] of integer;
n,i,j,k,l:integer;
file1:file of integer;
Procedure Floyd;
var i,j,m:integer;
begin
for i:=1 to n do
for j:=1 to n do
begin
S[i,j]:=G[i,j];
if G[i,j]=-1 then W[i,j]:=0
else W[i,j]:=j;
end;
for i:=1 to n do
for j:=1 to n do
for m:=1 to n do
if ((i<>j) and (S[j,i]<>-1) and (i<>m) and (S[i,m]<>-1) and ((S[j,m]=-1)
or (S[j,m]>S[j,i]+S[i,m]))) then
begin
W[j,m]:=W[j,i];
S[j,m]:=S[j,i]+S[i,m];
end;
end;
Procedure ShowWay(u,v:integer);
var x:integer;
begin
x:=u;
write(x,'');
while (x<>v) do
begin
x:=W[x,v];
write('--',x);
end;
end;
begin
assign(file1,'d:\mass.txt');
reset(file1);
clrscr;
writeln('vvedite pozhaluysta kolichestvo gorodov n');
readln(n);
for i:=1 to n do
for j:=1 to n do
if i<>j then
begin
writeln('vvedite dlinu dorogi mezhdu ',i,'-im i ',j,'-im gorodami');
read(file1,G[i,j]);
end;
writeln('vvedite pozhaluysta nuzhnie goroda k i l');
readln(k,l);
if (k>n) or (l>n) then
begin
writeln('takih gorodov prosto ne suschestvuyet');
readln;
exit;
end;
floyd;
showway(k,l);
writeln(' kratchaishiy put raven= ',S[k,l]);
readln;
close(file1);
end.




Добавлено через 3 мин.
Вот и все... Спасибо Мисс Графити за помощь, программа работает читая значения длин из файла... Вот и все с курсовой... cool.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.