Форум программистов, компьютерный форум, киберфорум
Delphi для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
Zidan
1

Поиск кратчайшего пути по городам

08.03.2012, 12:39. Просмотров 1080. Ответов 1
Метки нет (Все метки)

Посредством random задается симметричная матрица размерностью n (n - количество городов).
По умолчанию находимся в первом городе. Находим минимальное число в первой строке матрицы, допустим оно в 4м столбце. Значит минимальный путь от первого города идет к четвертому городу. Обнуляем только что найденный минимум в матрице (и вообще весь столбец, что бы в этот город больше не возвращаться. Затем ищем минимальный путь от 4го города и так далее.

В итоге должно получиться 5 чисел, (например: от 1го до 4го города, от 4го до 3го, от 3го до 5го, от 5го до 2го, от 2го до 1го)
На деле первые 3 числа правильно находятся и отображаются. 4е число иногда записывается как 0, а иногда нормально находится. 5 число это единственный оставшийся путь обратно до 1го города, и вообще первый столбец толжен учитываться только на этом последнем шаге.
Вот его я вообще не могу сделать =)
Все вычисления сделаны в подпрограмме, а задание массива и вывод результата в основной программе, таковы требования)

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
procedure TForm1.Button1Click(Sender: TObject);
  var i,j,e:Integer;
  c:array [1..50,1..50] of Integer;
  x:array [1..50] of Integer;
  q:array [1..50] of Integer;
 
  procedure pp(const n:Integer);
  var l,i,j,v,t,f,u,m,min:Integer;
  begin
    for l:=1 to n do
      q[l]:=c[l,1];
       i:=1;
       j:=1;
       v:=1;
       t:=0;
    while t<=n do
    begin
   if c[i,j]=0 then
   begin
   j:=j+1;
   min:=c[i,j];
   end
   else
   begin
   min:=c[i,j];
 
   end;
      f:=j;
   for u:=1 to n do
   begin
      if (c[i,u]<>0) and (c[i,u]<min) then
         begin
            min:=c[i,u];
            f:=u;
         end;
   end;
   c[i,f]:=0;
   c[f,i]:=0;
   i:=f;
   x[v]:=min;
   v:=v+1;
   t:=t+1;
   for m:=1 to n do
   begin
   c[m,f]:=0;
   c[m,1]:=0;
   end;
    end;
  end;
 
   begin
  n:=StrToInt(edt1.text);
  StringGrid1.RowCount := n+1;
  StringGrid1.ColCount := n+1;
  for i:=1 to n do
  for j:=1 to n do
        begin
       if i=j then
       c[i,j]:=0
       else
       begin
       c[i,j]:=(Random(20)+1);
       c[j,i]:=c[i,j];
       end;
       StringGrid1.Cells[j, i]:=IntToStr(c[i,j]);
       StringGrid1.Cells[i, j]:=IntToStr(c[i,j]);
       end;
          pp(n);
   for e:=1 to n do
   StringGrid2.Cells[e, 1]:=IntToStr(x[e]);
end;
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.03.2012, 12:39
Ответы с готовыми решениями:

Поиск кратчайшего пути в графе
unit road2_; interface uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms,...

Поиск кратчайшего пути в графе
помогите сделать так чтобы в весе графа можно было вписывать не только целый числа, но и дробные....

Поиск кратчайшего пути в графе.
unit road2_; interface uses Windows, Messages, SysUtils, Classes, Graphics, Controls,...

Поиск кратчайшего пути в графе
помогите пожалуйста с реализацией Нахождение кратчайшего пути для ориентированного графа.

1
401 / 312 / 74
Регистрация: 17.03.2010
Сообщений: 1,120
08.03.2012, 18:43 2
Читай теорию по поиску пути в графе!!!!
Например тут:
Найти путь в лабиринте
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.03.2012, 18:43

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Поиск кратчайшего пути с отображением рисунка
Очень нужна помощь! На первом курсе дали курсач с темой &quot;Поиск кратчайшего пути с отображением...

Определение кратчайшего пути алгоритмом Дэйстри
Разработка программного комплекса для определения кратчайшего пути алгоритмом Дэйстри. Программный...

Найдите массив с результатами кратчайшего пути
помогите в вопросе! нашел исходник программы находящей кратчайший путь. я пока еще новичок ! не...

Поиск кратчайшего пути
Всем доброго времени суток! Скажите, пожалуйста. Есть ли какие-то принципиальные отличия волнового...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.