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

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

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

Author24 — интернет-сервис помощи студентам
Поиск кратчайшего пути, а также обход в глубь для поиска всех путей.
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
13.02.2010, 21:47
Ответы с готовыми решениями:

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

алгоритм форда-беллмана в pascal
Здравствуйте. Имеется у меня такой вопрос. Вот есть алгоритм форда-беллмана {Bellman-Ford algorithm} var a : array of word;{matrica...

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

3
 Аватар для Tom_Sawyer
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
02.11.2011, 17:27
Помогаю со студенческими работами здесь

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

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

Метод Форда-Беллмана
Кто сможет помогите пожалуйста нужно составить программу реализации метода Форда-Беллмана нахождения кратчайшего пути в графе и при этом...

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

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


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

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

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Опции темы

Новые блоги и статьи
Язык программировани­я C++: сравнение с другими языками
Programming 06.02.2025
Современная разработка программного обеспечения предлагает множество языков программирования, каждый из которых обладает уникальными характеристиками и областями применения. C++ занимает особое место. . .
Язык программировани­­­я C++: достоинства и недостатки
Programming 06.02.2025
C++ считается одним из самых влиятельных языков программирования, продолжающим занимать ведущие позиции в мире разработки программного обеспечения. Этот язык появился как расширение языка C с. . .
Регулярные выражения в Python
BasicMan 06.02.2025
Регулярные выражения - это последовательности символов, определяющие правила поиска и сопоставления текстовых данных. В Python они используются для поиска подстрок, проверки соответствия текста. . .
Как создать свой мод для Майнкрафт с нуля на Java
IT_Exp 06.02.2025
Разработка мода для Minecraft начинается с правильной настройки среды разработки. Для создания мода потребуется Java Development Kit (JDK), интегрированная среда разработки и Minecraft Forge. JDK. . .
Async/await и асинхронное программировани­е в Java
IT_Exp 06.02.2025
Асинхронное программирование - это подход к организации вычислительных процессов, позволяющий приложениям эффективно использовать доступные ресурсы системы. В контексте Java этот метод приобретает. . .
Как исправить android.os.Netw­orkOnMain­Thread­Exception
hw_wired 06.02.2025
Исключение NetworkOnMainThreadException возникает при попытке выполнить сетевые операции в главном потоке Android-приложения. Главный поток отвечает за обработку пользовательского интерфейса и должен. . .
Как в Java определить, что массив содержит определенное значение
hw_wired 06.02.2025
В Java класс Arrays предлагает несколько способов для проверки наличия значений в массивах. Наиболее широко применяемый метод заключается в использовании комбинации Arrays. asList() и contains(). . . .
Как использовать virtualenv в Python. Виртуальные среды/окружения
hw_wired 06.02.2025
В Python виртуальные окружения решают одну из ключевых задач разработки - изоляцию зависимостей между проектами. Virtualenv создает отдельное пространство для каждого проекта, где устанавливаются. . .
Кнопка в HTML, которая работает как ссылка
hw_wired 06.02.2025
В HTML существует несколько подходов к созданию кнопки, которая функционирует как ссылка. Базовым элементом выступает тег button, который можно преобразовать в ссылку с помощью JavaScript. Для этого. . .
Как обновить страницу с помощью JavaScript
bytestream 06.02.2025
JavaScript предоставляет несколько базовых методов для обновления веб-страницы, которые встроены непосредственно в язык и доступны через объектную модель браузера. Основной метод обновления страницы. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru