Версия для печати темы

Автор: Dmitriy 15.04.2007 5:28

Народ, помогите решить плиз. Имеется 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

спасибо, разобрался, как запрограммирую так и код размещу(надеюсь)

Автор: 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 мин.
Вот и все... Спасибо Мисс Графити за помощь, программа работает читая значения длин из файла... Вот и все с курсовой...