Форум по Delphi программированию

Delphi Sources



Вернуться   Форум по Delphi программированию > Все о Delphi > [ "Начинающим" ]
Ник
Пароль
Регистрация <<         Правила форума         >> FAQ Пользователи Календарь Поиск Сообщения за сегодня Все разделы прочитаны

Ответ
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 04.05.2018, 22:13
DayBreak DayBreak вне форума
Прохожий
 
Регистрация: 20.03.2018
Сообщения: 10
Версия Delphi: Delphi 7
Репутация: 10
По умолчанию Кратчайший маршрут по матрице смежности

Всем привет,пытаюсь реализовать алгоритм Флойда для поиска кратчайшего маршрута(не пути).Алгоритм модифицированный и взят с вики,но как только я его написал,программа начала постоянно виснуть.Может у кого-нибудь есть мысли по реализации поиска кратчайшего маршрута(последовательность вершин) между двумя вершинами графа.В графе 0-если нет ребра и 1 если есть ребро.
https://neerc.ifmo.ru/wiki/index.php...%D0%B4%D0%B 0
Вот моя попытка
UPD:у меня там в комментариях несколько попыток написать алгоритм
Код:
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
unit Unit1;
 
interface
 
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Grids, StdCtrls, ExtCtrls, Buttons, Spin;
 
type
  TForm1 = class(TForm)
    StringGrid1: TStringGrid;
    BitBtn1: TBitBtn;
    PaintBox1: TPaintBox;
    Button1: TButton;
    SpinEdit1: TSpinEdit;
    StaticText1: TStaticText;
    Button2: TButton;
    Memo1: TMemo;
    procedure FormCreate(Sender: TObject);
    procedure BitBtn1Click(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure FormClose(Sender: TObject; var Action: TCloseAction);
    procedure PaintBox1Paint(Sender: TObject);
    procedure Button2Click(Sender: TObject);
     
 
  private
    { Private declarations }
  public
    { Public declarations }
  end;
 
type
  TMatrix=array {of array} [0..100,0..100] of Integer;
 
var
  Form1: TForm1;
  MaxN:Integer; //кол-во вершин
  Grath,Path,p:TMatrix;
  Bmp:TBitMap;
 
implementation
 
{$R *.dfm}
 
procedure TForm1.FormCreate(Sender: TObject);
begin
  StringGrid1.ColCount:=4;
  StringGrid1.RowCount:=4;
  StringGrid1.DefaultColWidth:=35;
  StringGrid1.DefaultRowHeight:=35;
  Bmp:=TBitmap.Create();
  Randomize();
 
end;
 
procedure TForm1.BitBtn1Click(Sender: TObject);
var
  i,j:Integer;
begin
  MaxN:=SpinEdit1.Value;
  StringGrid1.ColCount:=MaxN{+1};
  StringGrid1.RowCount:=MaxN{+1};
 
 { //нумерация
  for i:=1 to MaxN do
  begin
    StringGrid1.Cells[i,0]:=IntToStr(i);
    StringGrid1.Cells[0,i]:=IntToStr(i);
  end;    }
 
   for i:=0 to MaxN-1 do
     for j:=0 to MaxN-1 do
     StringGrid1.Cells[i,j]:='0';
 
end;
 
{procedure TForm1Drawing(var Grath:TMatrix;const MaxN:Integer; PaintBox:TPaintBox);
var
  i,j:Integer;
begin
  with PaintBox do
  begin
    PaintBox.Canvas.Brush.Color:=clWhite;
    PaintBox.Canvas.Rectangle(0,0,PaintBox.Width,PaintBox.Height);
    PaintBox.Canvas.Pen.Color:=clBlack;
    PaintBox.Canvas.Pen.Width:=2;
  end;
 
end;  }
 
procedure TForm1.Button1Click(Sender: TObject);
var
u,v,c,k, i,j:Integer;
  X,Y:array {[0..100] } of Integer;
begin
   MaxN:=SpinEdit1.Value;
   SetLength(X,MaxN);
   SetLength(Y,MaxN);
//   SetLength(Grath,MaxN,MaxN);
 
  for i:=0 to MaxN-1 do
    for j:=0 to MaxN-1 do
      if StringGrid1.Cells[i,j]<>'0' then StringGrid1.Cells[i,j]:='1';
      if i=j then StringGrid1.Cells[i,j]:='0';
    //  Grath[i,j]:=StrToInt(StringGrid1.Cells[i,j]);
 
 
 
  for i:=0 to MaxN-1 do
    for j:=0 to MaxN-1 do
      begin
        Grath[i,j]:=StrToInt(StringGrid1.Cells[i,j]);
        Path[i,j]:=Grath[i,j]; //копия матрицы смежности,в будущем участвует в алгоритме Флойда
      end;
 
  with Bmp do
  begin
    Height:=PaintBox1.Height;
    Width:=PaintBox1.Width;
    Canvas.Brush.Color:=clWhite;
    Canvas.Pen.Color:=clBlack;
    Canvas.FillRect(Rect(0,0,Width,Height));
 
 
  end;
 
  for i:=0 to MaxN-1 do
    begin
      X[i]:=Random(Bmp.Width); {random(200)+50;  }
      Y[i]:=Random(Bmp.Height);         {random(200)+50;}
    end;
 
     for i:=0 to MaxN-1 do
      for j:=0 to MaxN-1 do
      begin
        if Grath[i,j]=1 then
        begin
          with Bmp do
          begin
            Canvas.Pen.Color:=clBlack;
            Canvas.MoveTo(X[i],Y[i]);
            Canvas.LineTo(X[j],Y[j]);
          end;
          end;
      end;
 
 
    for i:=0 to MaxN-1 do
      begin
      with Bmp do
      begin
        Canvas.Brush.Color:=RGB(192, 192, 192);
        Canvas.Ellipse(X[i]-15, Y[i]-15, X[i]+15, Y[i]+15);
        Canvas.TextOut(X[i]-3, Y[i]-8, IntToStr(i+1));
      end;
    end;
    PaintBox1.Invalidate();
 //---------------------------------------------------------------------------------
 //дальше идет кусок кода,который убивает программу,а именно алгоритм Флойда
 //все,что идет до этого-работает и рисует граф
    for k:=0 to MaxN-1 do
      for u:=0 to MaxN-1 do
        for v:=0 to MaxN-1 do
          if (Path[u,k]+Path[k,v] < Path[u,v]) then
            begin
              Path[u,v]:=Path[u,k]+Path[k,v];
              p[u,v]:=p[u,k];            { p[i,j]:=k; }
            end;
 
  for u:=0 to  MaxN-1 do
     for v:=0 to MaxN-1 do
       StringGrid1.Cells[u,v]:=IntToStr(p[v,u]);  {IntToStr(p[j,i]);  }
 
  u:=2;
  v:=4;
  c:=u;
 
  while u<>v do
    begin
      for k:=0 to 15 do
      begin
        if Path[u,k]=Path[k,v] then Form1.Memo1.Text:=IntToStr(u)+'';
        u:=k;
        Break;
      end;
    end;
 
 
  Form1.Memo1.Text:=IntToStr(v)+'';
 { while c<>v do
  begin
    Form1.Memo1.Text:=(IntToStr(c)+'->');
    c:=p[c,j];
    Form1.Memo1.Text:=(IntToStr(v)+'->');
    Dec(c);
  end;    }
 { while j>0 do
  begin
    Form1.Memo1.Text := IntToStr(j) + ' ' + Form1.Memo1.Text;
    j:=p[i,j];
    Dec(j);
  end; }
 //------------------------------------------------------------------------конец
end;
 
 
 
procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);
begin
  Bmp.Free();
end;
 
 
 
 
procedure TForm1.PaintBox1Paint(Sender: TObject);
 
begin
  PaintBox1.Canvas.Draw(0,0,Bmp);
 // PaintBox1.Invalidate();
end;
 
 
procedure TForm1.Button2Click(Sender: TObject);
var
  i,j:Integer;
begin
  MaxN:=SpinEdit1.Value;
 
  for i:=0 to MaxN-1 do
    for j:=0 to MaxN-1 do
      StringGrid1.Cells[i,j]:=IntToStr(Random(2));   //рандомные значения в клетках
 
  for i:=0 to MaxN-1 do
    StringGrid1.Cells[i,i]:='0';   //диагональ - нули
 
end;
 
end.

Последний раз редактировалось DayBreak, 04.05.2018 в 22:20.
Ответить с цитированием
Ответ


Delphi Sources

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB-коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход


Часовой пояс GMT +3, время: 15:05.


 

Сайт

Форум

FAQ

Соглашения

Прочее

 

Copyright © Форум "Delphi Sources" by BrokenByte Software, 2004-2025