Народ, помогите решить плиз. Имеется N городов. Некоторые из них соединены дорогами известной длины. Система дорог моделируется матрицей N*N , элемент Аi,j равен -1, если соответсвующие I и J города не соединены прямой дорогой, или числу=длине дороги в противном случае. Программа поиска кратчайшего пути между K и L городами.
мисс_граффити
15.04.2007 5:41
Алгоритм не задан? У меня есть лабораторка по дискретке, где один из алгоритмов реализуется. Но не программкой, а просто вручную. Хотя все довольно легко (на первый взгляд, во всяком случае) кодируется. Если хочешь, скинь в личку свое мыло - я отправлю (там doc-файл).
Dmitriy
15.04.2007 17:42
Алгоритм не задан. Единственное о чем догадываюсь кроме алгоритма так называемой волны - это о том что длины нужно хранить во вспомогательном массиве. Буду весьма признателен за алгоритм.
мисс_граффити
15.04.2007 17:58
Проверяй мыло. Если что непонятно - спрашивай...
Dmitriy
15.04.2007 19:04
Цитата(мисс_граффити @ 15.04.2007 13:58)
Проверяй мыло. Если что непонятно - спрашивай...
спасибо, разобрался, как запрограммирую так и код размещу(надеюсь)
Dmitriy
3.05.2007 4:40
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 мин. Вот и все... Спасибо Мисс Графити за помощь, программа работает читая значения длин из файла... Вот и все с курсовой...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.