1 / 1 / 1
Регистрация: 06.01.2013
Сообщений: 266
1

Алгоритм Беллмана-Форда - выбор стартовой вершины

14.03.2016, 15:53. Показов 1276. Ответов 2
Метки нет (Все метки)

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

Pascal
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
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;
 
write('Стартовая вершина > ');
read(start);
writeln('Список кратчайших путей:');
FB(n, start);
end.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.03.2016, 15:53
Ответы с готовыми решениями:

Алгоритм Форда-Беллмана
У меня есть код алгоритма, но мне его надо переделать так, чтобы я сам вводил матрицу ( состоящую...

Алгоритм Форда-Беллмана.
Поиск кратчайшего пути, а также обход в глубь для поиска всех путей.

Алгоритм Форда-Беллмана
Народ если есть у кого нибудь исходник выложите пожалуйста очень надо. А то везде одно и то же......

Алгоритм Беллмана-Форда
Здравствуйте. Может ли быть на входе доя алгоритма Беллмана-Форда граф, состоящий из ДВУХ вершин?...

2
1 / 1 / 1
Регистрация: 06.01.2013
Сообщений: 266
18.03.2016, 22:05  [ТС] 2
Никто не знает?
0
Модератор
Эксперт по электронике
8291 / 4194 / 1597
Регистрация: 01.02.2015
Сообщений: 13,037
Записей в блоге: 4
19.03.2016, 10:05 3
Описание на e-maxx - http://e-maxx.ru/algo/ford_bellman.
Там и описание и восстановление пути.

Добавлено через 9 минут
Цитата Сообщение от fkty Посмотреть сообщение
Как можно сделать,чтобы не выбирать стартовую вершину, а чтобы результат выводился по всем вершина в в виде таблицы? И для любой пары вершин найти сам путь кратчайшей длины?
Если я правильно понял, то нужно вызвать алгоритм для каждой вершины, а результат работы сохранить в виде, аналогичном для алгоритма Флойда-Уоршелла.
--------------------------------------------
Надеюсь, что за прошедшую неделю вы удосужились почитать методичку и материалы в интернет, а также освежили память по лекциям.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.03.2016, 10:05
Помогаю со студенческими работами здесь

Алгоритм Форда-Беллмана
Доброго времени суток. Есть кривой код: #include &lt;iostream&gt; #include &lt;vector&gt; using namespace...

Алгоритм Беллмана - Форда
Подскажите, я вроде бы посчитал правильно но конечный результат в таблице я так и не понял. Какой...

Алгоритм Беллмана-Форда
Здравствуйте, уже какой день мучаюсь с реализацией этого алгоритма в С#, прочитал Википедию и мн-во...

Алгоритм Беллмана-Форда
Здравствуйте всем. Я вообще редко обращаюсь сюда за помощью решить задачу и стыдно как то, но я не...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru