Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 14.03.2016, 16:59   #1
fkty
Форумчанин
 
Регистрация: 22.05.2013
Сообщений: 245
По умолчанию Алгоритм Беллмана-Форда

Здравствуйте, помогите пожалуйста доделать задачу алгоритм Беллмана-Форда.
Как можно сделать,чтобы результат выводился по всем вершина в в виде таблицы (матрицы)? И для любой пары вершин найти сам путь кратчайшей длины?

Код:
program Ford_Bellman; 
uses crt; 
const 
inf=100000; 
Vmax=1000; 
Emax=Vmax*(Vmax-1) div 2; 
type Edges=record 
u, v, w: integer; 
end; 
Var 
e, n, w, start: integer; 
edge: array[1..Emax] of Edges; 
d: array[1..Vmax] of integer; 

{алгоритм Беллмана-Форда} 
procedure FB(n, s: integer); 
var i,j:integer; 
begin 
for i:=1 to n do 
d[i]:=inf; 
d[s]:=0; 

for i:=1 to n-1 do 
for j:=1 to e-1 do 
if d[edge[j].v]+edge[j].w<d[edge[j].u] then 
d[edge[j].u]:=d[edge[j].v]+edge[j].w; 


for i:=1 to n do if d[i]=inf then 
writeln(start, '->', i, '=', 'Not') 
else writeln(start, '->', i, '=', d[i]); 
end; 

{основной блок программы} 
var i,j:integer; 
begin 
clrscr; 
write('Введите количество вершин > '); 
read(n); 
e:=1; 

for i:=1 to n do 
for j:=1 to n do 
begin 
write('Вес ', i, '->', j, ' > '); 
read(w); 
if w<>0 then 
begin 
edge[e].v:=i; 
edge[e].u:=j; 
edge[e].w:=w; 
e:=e+1; 
end; 
end; 

start:=1; 
for i:=1 to n do 

begin 
writeln('Список кратчайших путей:'); 

FB(n, start); 
start:=start+1; 
end; 
end.
fkty вне форума Ответить с цитированием
Старый 15.03.2016, 16:49   #2
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
Как можно сделать,чтобы результат выводился по всем вершина в в виде таблицы (матрицы)?
Уже так и выводится
Цитата:
И для любой пары вершин найти сам путь кратчайшей длины?
Так и будет в матрице
Poma][a вне форума Ответить с цитированием
Старый 15.03.2016, 18:59   #3
fkty
Форумчанин
 
Регистрация: 22.05.2013
Сообщений: 245
По умолчанию

Poma][a, сейчас там выводится все в строчку,а не как матрица. А найти сам путь кратчайшей длины имеется в виду через какие вершины проходит этот путь (например выбираем вершину 1 и 4, чтобы попасть из вершины 1 в 4 нужно пройти через вершины 2 и з, тогда выводить нужно 1,2,3,4 - кратчайший путь)
fkty вне форума Ответить с цитированием
Старый 15.03.2016, 23:46   #4
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Путь восстанавливается через массив предков
Poma][a вне форума Ответить с цитированием
Старый 18.03.2016, 22:04   #5
fkty
Форумчанин
 
Регистрация: 22.05.2013
Сообщений: 245
По умолчанию

А как это сделать?
fkty вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

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

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск кратчайшего пути.Метод Форда-Беллмана xbron Паскаль, Turbo Pascal, PascalABC.NET 0 08.12.2013 16:20
алгоритм Форда-Беллмана [язык - C] dixonich Помощь студентам 0 13.05.2012 14:37
Алгоритм Беллмана-форда,нахождение кратчайшего пути bakir Помощь студентам 1 13.01.2010 02:31
Алгоритм Форда-Беллмана k1r1ch Помощь студентам 2 27.12.2009 20:10
алгоритм Форда-Беллмана Foky Паскаль, Turbo Pascal, PascalABC.NET 1 19.10.2008 17:27