0 / 0 / 1
Регистрация: 07.02.2010
Сообщений: 11
1

Алгоритм Форда-Беллмана.

13.02.2010, 21:47. Показов 10510. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Поиск кратчайшего пути, а также обход в глубь для поиска всех путей.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.02.2010, 21:47
Ответы с готовыми решениями:

Поиск максимального потока методом Форда-Фалкерсона
Здрасвуйте помогите мне пожалуйста найти поиск максимального потока методом Форда-Фалкерсона; для...

алгоритм форда-беллмана в pascal
Здравствуйте. Имеется у меня такой вопрос. Вот есть алгоритм форда-беллмана {Bellman-Ford...

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

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

3
88 / 88 / 56
Регистрация: 05.12.2009
Сообщений: 134
13.02.2010, 22:05 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
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
var a:array[1..20,1..20] of word; {матрица смежности}
c,pred,fl,d:array[1..20] of word;{c - массив кратчайших расстояний; pred - массив предыдущих вершин; fl - массив флагов; d - массив для записи пути}
i,j,k,n,first,last:byte;
f:text;{переменная для открытия in.txt}
 
{процедура обхода графа вглубь для поиска всех путей}
 
Procedure Dfs(x:word); {в качестве параметра передаём текущую вершину}
var i:byte; {локальная переменная}
begin
 if x=last then {если конечная вершина, то вводим путь}
  begin
   write(first,' ');
   for i:=1 to j do {выводим путь}
    write(d[i],' ');
    writeln;
    exit;{выходим из процедуры}
  end;
 fl[x]:=1; {помечаем что были в вершине}
 for i:=1 to n do {если не были в вершине и существует дуга в неё}
  if (fl[i]=0)and(a[x,i]<>32767) then
   begin
    inc(j);
    d[j]:=i; {записываем в путь вершину}
    dfs(i); 
    dec(j);
   end;
 fl[x]:=0; {помечаем что вершина свободна}
end;
 
{основная программа}
 
begin
     assign(f,'in.txt'); {открываем файл для чтения}
     reset(f);
     readln(f, n); {считываем количество вершин}
     for i:=1 to n do
          for j:=1 to n do
          read(f,a[i,j]); {считываем матрицу смежности}
     writeln('Mатрица:');
     for i:=1 to n do  {выводим матрицу на экран}
          for j:=1 to n do
           if j=n then writeln(a[i,j])
           else write(a[i,j],' ');
     for i:=1 to n do {заменяем нули бесконечностью}
          for j:=1 to n do
          if a[i,j]=0 then a[i,j]:=32767;
     writeln('Введите 1 вершину: ');
     readln(first);
     writeln('Введите 2 вершину');
     readln(last);
     close(f); {закрываем файл in.txt}
     for j:=1 to n do
     begin
           c[j]:=a[first,j]; {записываем начальные значения}
           if a[first,j]<32767 then
           pred[j]:=first; {если существует дуга то записываем предыдущую вершину}
     end;
     for i:=3 to n do
         for j:=1 to n do
             if j<>first then
             for k:=1 to n do  {если не бесконечность и путь более выгодный}
                 if (c[k]<32767) and (c[k]+a[k,j]<c[j]) then
                  begin
                   c[j]:=c[k]+a[k,j]; {записываем новое значение}
                   pred[j]:=k; {записываем pred вершину}
                  end;
     if c[last]=32767 then writeln('Нет путей') 
     else {если бесконечность то нет пути}
      begin
          writeln;
          writeln('Кратчайший путь:');
          write(first,' ');
          i:=last;
          k:=1;
          while i<>first do {в обратном порядке обходим путь}
           begin
               d[k]:=i; {записываем путь в массив}
               k:=k+1;
               i:=pred[i];
           end;
          for i:=k-1 downto 1 do {выводим кратчайший путь}
          write(d[i],' ');
          writeln;
          writeln('Все пути:');
          j:=0;
          Dfs(first); {вызываем процедуру поиска всех путей}
      end;
     readln;
     readln;
end.
6
0 / 0 / 1
Регистрация: 07.02.2010
Сообщений: 11
13.02.2010, 23:51  [ТС] 3
Tom_Sawyer, Спасибо превеликое!!!!!!!!
0
2 / 2 / 2
Регистрация: 03.03.2010
Сообщений: 139
02.11.2011, 17:27 4
Цитата Сообщение от Tom_Sawyer Посмотреть сообщение
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
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
var a:array[1..20,1..20] of word; {матрица смежности}
c,pred,fl,d:array[1..20] of word;{c - массив кратчайших расстояний; pred - массив предыдущих вершин; fl - массив флагов; d - массив для записи пути}
i,j,k,n,first,last:byte;
f:text;{переменная для открытия in.txt}
 
{процедура обхода графа вглубь для поиска всех путей}
 
Procedure Dfs(x:word); {в качестве параметра передаём текущую вершину}
var i:byte; {локальная переменная}
begin
 if x=last then {если конечная вершина, то вводим путь}
  begin
   write(first,' ');
   for i:=1 to j do {выводим путь}
    write(d[i],' ');
    writeln;
    exit;{выходим из процедуры}
  end;
 fl[x]:=1; {помечаем что были в вершине}
 for i:=1 to n do {если не были в вершине и существует дуга в неё}
  if (fl[i]=0)and(a[x,i]<>32767) then
   begin
    inc(j);
    d[j]:=i; {записываем в путь вершину}
    dfs(i); 
    dec(j);
   end;
 fl[x]:=0; {помечаем что вершина свободна}
end;
 
{основная программа}
 
begin
     assign(f,'in.txt'); {открываем файл для чтения}
     reset(f);
     readln(f, n); {считываем количество вершин}
     for i:=1 to n do
          for j:=1 to n do
          read(f,a[i,j]); {считываем матрицу смежности}
     writeln('Mатрица:');
     for i:=1 to n do  {выводим матрицу на экран}
          for j:=1 to n do
           if j=n then writeln(a[i,j])
           else write(a[i,j],' ');
     for i:=1 to n do {заменяем нули бесконечностью}
          for j:=1 to n do
          if a[i,j]=0 then a[i,j]:=32767;
     writeln('Введите 1 вершину: ');
     readln(first);
     writeln('Введите 2 вершину');
     readln(last);
     close(f); {закрываем файл in.txt}
     for j:=1 to n do
     begin
           c[j]:=a[first,j]; {записываем начальные значения}
           if a[first,j]<32767 then
           pred[j]:=first; {если существует дуга то записываем предыдущую вершину}
     end;
     for i:=3 to n do
         for j:=1 to n do
             if j<>first then
             for k:=1 to n do  {если не бесконечность и путь более выгодный}
                 if (c[k]<32767) and (c[k]+a[k,j]<c[j]) then
                  begin
                   c[j]:=c[k]+a[k,j]; {записываем новое значение}
                   pred[j]:=k; {записываем pred вершину}
                  end;
     if c[last]=32767 then writeln('Нет путей') 
     else {если бесконечность то нет пути}
      begin
          writeln;
          writeln('Кратчайший путь:');
          write(first,' ');
          i:=last;
          k:=1;
          while i<>first do {в обратном порядке обходим путь}
           begin
               d[k]:=i; {записываем путь в массив}
               k:=k+1;
               i:=pred[i];
           end;
          for i:=k-1 downto 1 do {выводим кратчайший путь}
          write(d[i],' ');
          writeln;
          writeln('Все пути:');
          j:=0;
          Dfs(first); {вызываем процедуру поиска всех путей}
      end;
     readln;
     readln;
end.
Напишите пример содержимого файла а то у меня выводит 201 ошибку
0
02.11.2011, 17:27
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.11.2011, 17:27
Помогаю со студенческими работами здесь

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

Метод Форда-Беллмана
Кто сможет помогите пожалуйста нужно составить программу реализации метода Форда-Беллмана...

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

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


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

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

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