Всем привет!
Делаю алгоритм Алгоритм Форда-Беллмана по примеру:
http://cybern.ru/algoritm-forda-bell...hi-pascal.html
Данный код может показать минимальное расстояние из одной вершины до всех остальных. А через какие вершины он при этом прошел не говорит. Как можно изменить код, чтобы показывал вершины через которые прошел? Заранее спасибо!
Код:
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 | {$APPTYPE CONSOLE}
const
inf = $7FFFFFFF ;
type
TEdge = record
from: integer ;
to1: integer ;
l: integer ;
end ;
var
n, m, i, j, v: integer ;
t: array [ 0 .. 1000 ] of longint ;
edges: array [ 0 .. 10000 ] of TEdge;
begin
read(n);
readln(m);
for i := 0 to m - 1 do
begin
read(edges[i].from, edges[i].to1);
readln(edges[i].l);
dec(edges[i].from);
dec(edges[i].to1);
end ;
readln(v);
dec(v);
for i := 0 to n - 1 do
t[i] := inf;
t[v] := 0 ;
for i := 1 to n do
for j := 0 to m - 1 do
if (t[edges[j].from] < inf) and
(t[edges[j].from] + edges[j].l < t[edges[j].to1]) then
if i = n then
begin
writeln ( 'INCORRECT INPUT' );
exit;
end
else
t[edges[j].to1] := t[edges[j].from] + edges[j].l;
for i := 1 to n - 1 do
begin
if (t[i] = inf) then
writeln ( 'NO' )
else
writeln (t[i]);
end ;
end .
|