ЧакЭ одобряЭ
 Аватар для Artishok
285 / 284 / 86
Регистрация: 27.12.2009
Сообщений: 1,767

Алгоритм Форда-Фалкерсона, программа выводит ноль

30.11.2010, 13:10. Показов 2906. Ответов 4
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
в чем проблема?вроде матрица инициализируется раз выводит первоначальную матрицу

Не по теме:

это алгоритм форда-фалкерсона.


C++
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#define maxint 100000
 
int min(int a,int b)//äëÿ ïîèñêà ðåáðà ñ ìèíèìàëüíîé ïðîïóñêíîé ñïîñîáíîñòüþ
{
    if (a<b)
       return a;
    else
       return b;
}
 
/*Èçíà÷àëüíî âåëè÷èíå ïîòîêà ïðèñâàèâàåòñÿ çíà÷åíèå 0: f(u,v) = 0 äëÿ âñåõ . 
Çàòåì âåëè÷èíà ïîòîêà èòåðàòèâíî óâåëè÷èâàåòñÿ ïîñðåäñòâîì ïîèñêà óâåëè÷èâàþùåãî ïóòè 
(ïóòü îò èñòî÷íèêà s ê ñòîêó t, âäîëü êîòîðîãî ìîæíî ïîñëàòü áîëüøèé ïîòîê). 
Ïðîöåññ ïîâòîðÿåòñÿ, ïîêà ìîæíî íàéòè óâåëè÷èâàþùèé ïóòü.*/
 
/*
1)Îáíóëÿåì âñå ïîòîêè. Îñòàòî÷íàÿ ñåòü èçíà÷àëüíî ñîâïàäàåò ñ èñõîäíîé ñåòüþ.
2) îñòàòî÷íîé ñåòè íàõîäèì ëþáîé ïóòü èç èñòî÷íèêà â ñòîê. Åñëè òàêîãî ïóòè íåò, îñòàíàâëèâàåìñÿ.
3)Ïóñêàåì ÷åðåç íàéäåííûé ïóòü (îí íàçûâàåòñÿ óâåëè÷èâàþùèì ïóò¸ì èëè óâåëè÷èâàþùåé öåïüþ) ìàêñèìàëüíî âîçìîæíûé ïîòîê:
4)Íà íàéäåííîì ïóòè â îñòàòî÷íîé ñåòè èùåì ðåáðî ñ ìèíèìàëüíîé ïðîïóñêíîé ñïîñîáíîñòüþ cmin.
5)Äëÿ êàæäîãî ðåáðà íà íàéäåííîì ïóòè óâåëè÷èâàåì ïîòîê íà cmin, à â ïðîòèâîïîëîæíîì åìó - óìåíüøàåì íà cmin.
6)Ìîäèôèöèðóåì îñòàòî÷íóþ ñåòü. Äëÿ âñåõ ð¸áåð íà íàéäåííîì ïóòè, à òàêæå äëÿ ïðîòèâîïîëîæíûõ èì ð¸áåð, 
âû÷èñëÿåì íîâóþ ïðîïóñêíóþ ñïîñîáíîñòü. Åñëè îíà ñòàëà íåíóëåâîé, äîáàâëÿåì ðåáðî ê îñòàòî÷íîé ñåòè, 
à åñëè îáíóëèëàñü, ñòèðàåì åãî.
7)Âîçâðàùàåìñÿ íà øàã 2.*/
 
int put(int **mat,bool *v,int nach1,int kon1,int temp,int razm)//ïîèñê ïóòè îò òî÷êè ê òî÷êè
{   
  if (nach1==kon1)//ïóòü íàéäåí
   return temp;
  v[nach1]=true;//ïîìå÷àåì òî÷êó îòïðàâëåíèÿ
  for(int i=0;i<razm;i++)//äîëæíî îáîéòè âñå âåðøèíû.à êîë-âî âåðøèå razm
   if(!v[i]&&mat[nach1][i]>0)//åñëè íà äóãå åñòü åù¸ ìåñòî è âåðøèíà íå òà ÷åðåç êîòîðóþ óæå ïðîøëè
   {
    int def=put(mat,v,i,kon1,min(temp,mat[nach1][i]),razm);//èùåì ìèíèìàëüíîå ðåáðî è ýòî áóäåò ïðîïóñùåííûé ïîòîê
     if (def>0)//åñëè ïîòîê íåíóëåâîé.åãî íàäî ïðîïóñòèòü ÷åðåç âåðøèíó
     {
      mat[nach1][i] -=def;//6)
      mat[i][nach1] +=def;//6)
      return def;
     }
    }
    return 0;
}
 
int potok(int **mat,int nach,int kon,int razm)//ñîîáñâåííî ïîèñê ïîòîêà
{
  for(int flow=0;;)//îáíóëåíèå ïîòîêîâ.êîãäà çàêîí÷èòñÿ öèêë íåèçâåñòíî.ñ êàêèì øàãîì èçìåíÿòüñÿ òîæå íå èçâåñòíî
  {
   int ch=razm;
   bool ar[ch];//ìàññèâ ïîìåòîê âåðøèí
   int deff=put(mat,ar,nach,kon,maxint,razm);//èùåì ïóòü.âåðíåò çíà÷åíèå ïðîïóùåííîãî ïîòîêà
   if (deff==0)//åñëè åñëè óæå áîëüøå ïðîïóñòèòü íåëüçÿ
     return flow;//ìàêñèìàëüíûé ïîòîê âåðíåì
   flow+=deff;//óâåëè÷èâàåì ìàêèìàëüíûé ïîòîê
  }
}
    
int main()
{
    int razm=0;//ðàçìåð ìàòðèöû.ïåðâîíà÷àëüíî ðàâåí 0
    cout<<"Size of matrix"<<endl;
    cin>>razm;
    
    int **matrix=new int*[razm];
    for(int i=0;i<razm;i++)
     matrix[i]=new int[razm];
     
    cout<<"Insert elements"<<endl;  
    for(int i=0;i<razm;i++)
     for(int j=0;j<razm;j++)
      cin>>matrix[i][j];
      
    //òðàíñôîðìèðîâàíèå ìàòðèöû ê íåîáõîäèìîìó âèäó
    /*1)ïåòåëü íåò ïîýòîìó ýëåìåíòû ãëàâíîé äèàãîíàëè 0
      2)èç ëþáîé âåðùèíû íå ìîæåò èäòè â èñòîê
      3)èç ñòîêà íå èäåò íè÷åãî*/
      for(int i=0;i<razm;i++)
       for(int j=0;j<razm;j++)
        {
          //1)îáíóëåíèå äèàãîíàëè
          if (i==j)
            matrix[i][j]=0;
          //2)â èñòîê íå èäåò íè÷åãî
          matrix[i][0]=0;
        }
        //3)ñòðîêà matrix[razm][razm] ñîäåðæèò 0
        for(int j=0;j<razm;j++)
         matrix[razm-1][j]=0;
         
     cout<<"Matrix"<<endl;
     for(int i=0;i<razm;i++)
     {
      for(int j=0;j<razm;j++)
        cout<<matrix[i][j]<<" ";
       cout<<endl;
     }
     //ïðè ïîèñêå ìàêñèìàëüíîãî ïîòîêà íàäî ñëîæèòü âñå ïîòîêè êîòîðûå ìîæíî ê ñòîêó ïðîâåñòè.
     cout<<potok(matrix,0,(razm-1),razm)<<endl;
     
     for(int i=0;i<razm;i++)
     delete [] matrix[i];
     
     delete [] matrix;
     return 0;    
}
Добавлено через 3 часа 20 минут
help

Добавлено через 3 часа 31 минуту


Добавлено через 12 часов 50 минут
вот исходник на java если что
Java
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
public class MaxFlowFordFulkerson {
 
  static int findPath(int[][] cap, boolean[] vis, int u, int t, int f) {
    if (u == t)
      return f;
    vis[u] = true;
    for (int v = 0; v < vis.length; v++)
      if (!vis[v] && cap[u][v] > 0) {
        int df = findPath(cap, vis, v, t, Math.min(f, cap[u][v]));
        if (df > 0) {
          cap[u][v] -= df;
          cap[v][u] += df;
          return df;
        }
      }
    return 0;
  }
 
  public static int maxFlow(int[][] cap, int s, int t) {
    for (int flow = 0;;) {
      int df = findPath(cap, new boolean[cap.length], s, t, Integer.MAX_VALUE);
      if (df == 0)
        return flow;
      flow += df;
    }
  }
 
  // Usage example
  public static void main(String[] args) {
    int[][] capacity = { { 0, 3, 2 }, { 0, 0, 2 }, { 0, 0, 0 } };
    System.out.println(4 == maxFlow(capacity, 0, 2));
  }
}
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
30.11.2010, 13:10
Ответы с готовыми решениями:

Алгоритм Форда-Фалкерсона
Нужен код алгоритма Форда-Фалкерсона. Нигде не нашел рабочий вариант. А те, что нашел, не работают и содержат кучу мусора.

Входные данные. Метод Форда-Фалкерсона
Доброго времени суток! Есть код, который работает и справляется с основной задачей - нахождением максимального потока сети методом...

Алгоритм Форда-Фалкерсона
Здравствуйте дорогие друзья, не завалялась ли у вас где-нибудь реализация данного алгоритма на языке Лисп? Сам на лиспе не программирую и...

4
 Аватар для besstiaa
94 / 94 / 14
Регистрация: 04.06.2010
Сообщений: 223
30.11.2010, 13:37
Цитата Сообщение от Artishok Посмотреть сообщение
вроде матрица инициализируется раз выводит первоначальную матрицу
Хм... А у вас вообще компилируется этот код?
По крайней мере в функции potok нельзя объявить массив bool ar[ch], потому как ch не константа. Тут нужно использовать динамический массив.
1
ЧакЭ одобряЭ
 Аватар для Artishok
285 / 284 / 86
Регистрация: 27.12.2009
Сообщений: 1,767
30.11.2010, 13:44  [ТС]
компилируется.по стандарту C99 объявлять так можно
1
 Аватар для besstiaa
94 / 94 / 14
Регистрация: 04.06.2010
Сообщений: 223
30.11.2010, 14:10
А есть какие-нибудь конкретные примеры. Матрица такая-то, ответ должен быть такой-то, а то с транспортными сетями туго.

По крайней мере, если в функции potok все элементы массива ar приравнять к false, то по крайней мере уже не ноль. Однако насколько правильный ответ, сложно сказать. Я что-то до конца алгоритм не поняла.
0
ЧакЭ одобряЭ
 Аватар для Artishok
285 / 284 / 86
Регистрация: 27.12.2009
Сообщений: 1,767
30.11.2010, 19:59  [ТС]
а пример написан в коде java
032
002
000
и ответ 4
для большей сети есть тоже матрица.правда я там точный ответ не знаю
по сути код на java мало отличается от того же что я написал на си но не работает даже с примером который в коде

Добавлено через 1 час 51 минуту
Algorithm Ford–Fulkerson
1)Inputs Graph G with flow capacity c, a source node s, and a sink node t
2)Output A flow f from s to t which is a maximum
for all edges (u,v)
3)While there is a path p from s to t in Gf, such that cf(u,v) > 0 for all edges :
Find
For each edge
(Send flow along the path)
(The flow might be "returned" later)

вот суть этой реализации.перевести?
но пометка true означает что есть путь из вершины

Добавлено через 3 минуты
двумя фразами - рекурсивно просматривается есть ли путь из вершины в вершину.параллельно ищется минимальное ребро чтобы вычесть его размер из всех ребер пути как пропущенный поток

Добавлено через 3 минуты
Цитата Сообщение от besstiaa Посмотреть сообщение
то по крайней мере уже не ноль.
а какой ответ?

Добавлено через 4 минуты
О!верно однако.4 получается.проверим на чем-то помощнее...

Добавлено через 7 минут
работает теперь.
получается на java массив автоматически создавался из false?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
30.11.2010, 19:59
Помогаю со студенческими работами здесь

алгоритм форда-фалкерсона
Доброго времени суток, как можно реализовать алгоритм Форда-Фалкерсона в матрице? Размер матрицы может изменятся в зависимости от числа...

Алгоритм Форда-Фалкерсона
Нужно за алгоритмом Форда-Фалкерсона рассщитать максимальный поток транспортной сети(вложение). Помогите пожалуйста а то у меня не...

алгоритм Форда-Фалкерсона максимальный поток
какой компилятор лучше испольковать что бы запустить эту программу &gt; restart:with(networks): &gt;...

Алгоритм Форда-Фалкерсона максимальный поток
Для определения потока в сети используют алгоритм Форда-Фалкерсона: а) ищем любую цепь из истока графа в сток; б) каждой дуге...

Алгоритм Форда-Фалкерсона, максимальный поток в сети
Первое красное значение на пути это вес а второе поток. Проблема заключается в том что поток превышает вес. public class...


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

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

Новые блоги и статьи
sshd restrictions, ssh access limitations
jigi33 26.03.2025
sshd restrictions | ssh access limitations рестрикции доступа на сервер sshd статья: https:/ / www. golinuxcloud. com/ restrict-allow-ssh-certain-users-groups-rhel
Компиляция C++ с Clang API
NullReferenced 24.03.2025
Компиляторы обычно воспринимаются как черные ящики, которые превращают исходный код в исполняемые файлы. Мы запускаем компилятор командой в терминале, и вуаля — получаем бинарник. Но что если нужно. . .
Многопоточное программировани­е в C#: Класс Thread
UnmanagedCoder 24.03.2025
Когда запускается приложение на компьютере, операционная система создаёт для него процесс - виртуальное адресное пространство. В C# этот процесс изначально получает один поток выполнения — главный. . .
SwiftUI Data Flow: Передача данных между представлениями
mobDevWorks 23.03.2025
При первом знакомстве со SwiftUI кажется, что фреймворк предлагает избыточное количество механизмов для передачи данных: @State, @Binding, @StateObject, @ObservedObject, @EnvironmentObject и другие. . . .
Моки в Java: Сравниваем Mockito, EasyMock, JMockit
Javaican 23.03.2025
Как протестировать класс, который зависит от других сложных компонентов, таких как базы данных, веб-сервисы или другие классы, с которыми и так непросто работать в тестовом окружении? Для этого и. . .
Архитектурные паттерны микросервисов: ТОП-10 шаблонов
ArchitectMsa 22.03.2025
Популярность микросервисной архитектуры объясняется множеством важных преимуществ. К примеру, она позволяет командам разработчиков работать независимо друг от друга, используя различные технологии и. . .
Оптимизация рендеринга в Unity: Сортировка миллиона спрайтов
GameUnited 22.03.2025
Помните, когда наличие сотни спрайтов в игре приводило к существенному падению производительности? Время таких ограничений уходит в прошлое. Сегодня геймдев сталкивается с задачами совершенно иного. . .
Образование и практика
Igor3D 21.03.2025
Добрый день А вот каково качество/ эффективность ВУЗовского образования? Аналитическая геометрия изучается в первом семестре и считается довольно легким курсом, что вполне справедливо. Ну хорошо,. . .
Lazarus. Таблица с объединением ячеек.
Massaraksh7 21.03.2025
Понадобилась представление на экране таблицы с объединёнными ячейками. И не одной, а штук триста, и все разные. На Delphi я использовал для этих целей TStringGrid, и то, кривовато получалось. А в. . .
Async/await в Swift: Асинхронное программировани­е в iOS
mobDevWorks 20.03.2025
Асинхронное программирование долго было одной из самых сложных задач для разработчиков iOS. В течение многих лет мы сражались с замыканиями, диспетчеризацией очередей и обратными вызовами, чтобы. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru