Алгоритм Форда-Беллмана (реализация в Delphi/Pascal)

Pascal/Delphi   26 апреля 2012  Автор статьи: admin 

Задан ориентированный взвешенный граф, содержащий, возможно, дуги отрицательного веса. Необходимо найти веса кратчайших путей от вершины v до всех остальных вершин.

Входные данные:

В первой строке записаны целые числа N и M – количество вершин и количество дуг соответственно (2\le N\le 1000, 0\le M\le 10000). Дальше идет M строк с тройками целых чисел X, Y, W, обозначающими, что дуга из X в Y имеет вес W (1\le X,Y\le N, |W|\le 1000). В последней строке записано число v – номер стартовой вершины (1\le v\le N).

Выходные данные:
Если в графе есть циклы отрицательного веса и потому не все кратчайшие пути определены, вывести «INCORRECT INPUT». В противном случае вывести N строк – веса кратчайших путей от вершины v до всех остальных вершин, включая её саму, в порядке возрастания номера второй вершины. Если до вершины дойти нельзя, то в соответствующей строке необходимо вывести «NO».

Реализация решения

[cc lang=»delphi»]{$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.[/cc]

  • Vlad

    Что здесь делает алгоритм Форда-Беллмана? Это вообще связано со спортивным программированием. Зачем оно здесь?

Научиться программировать

  • на Delphi

  • на Java

  • на C++