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

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

11.01.2015, 17:03. Показов 12898. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Вложение 477161
Первое красное значение на пути это вес а второе поток.
Проблема заключается в том что поток превышает вес.
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 public class FordFulkerson
    {
        public FordFulkerson(int size)
        {
            NUM_VERTICES = size;
        }
        const int MAX_VERTICES = 14;
 
        int NUM_VERTICES; // число вершин в графе
        const int INFINITY = 10000; // условное число обозначающее бесконечность
 
        // f - массив садержащий текушее значение потока
        // f[i][j] - поток текущий от вершины i к j
        public int[,] f = new int[MAX_VERTICES, MAX_VERTICES];
        // с - массив содержащий вместимоти ребер,
        // т.е. c[i][j] - максимальная величину потока способная течь по ребру (i,j)
        public int[,] c = new int[MAX_VERTICES, MAX_VERTICES];
        // набор вспомогательных переменных используемых функцией FindPath - обхода в ширину
        // Flow - значение потока чарез данную вершину на данном шаге поиска
        int[] Flow = new int[MAX_VERTICES];
        // Link используется для нахождения собственно пути
        // Link[i] хранит номер предыдущей вешины на пути i -> исток
        int[] Link = new int[MAX_VERTICES];
        List<int> tmp = new List<int>();
        int[] Queue = new int[MAX_VERTICES]; // очередь
        int QP, QC; // QP - указатель начала очереди и QC - число эл-тов в очереди
 
        public void RecMas(int[,] a, int size)
        {
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    c[i, j] = a[i, j];
                }
            }
        }
 
        public int FindPath(int source, int target) // source - исток, target - сток
        {
            QP = 0; QC = 1; Queue[0] = source;
            Link[target] = -1; // особая метка для стока
            //int i;
            int CurVertex;
            //  memset(Flow, 0, sizeof(int) * NUM_VERTICES); // в начале из всех вершин кроме истока течет 0
            Array.Clear(Flow, 0, Flow.Length);
            Flow[source] = INFINITY; // а из истока может вытечь сколько угодно
            while (Link[target] == -1 && QP < QC)
            {
                // смотрим какие вершины могут быть достигнуты из начала очереди
                CurVertex = Queue[QP];
                for (int i = 0; i < NUM_VERTICES; i++)
                    // проверяем можем ли мы пустить поток по ребру (CurVertex,i):
                    if ((c[CurVertex, i] - f[CurVertex, i]) > 0 && Flow[i] == 0)
                    {
 
                        //  if (f[CurVertex, i] + f[Link[i - 1], CurVertex] > c[Link[i - 1], CurVertex])
                        {
                            // если можем, то добавляем i в конец очереди
                            Queue[QC] = i; QC++;
                            Link[i] = CurVertex; // указываем, что в i добрались из CurVertex
                            // и находим значение потока текущее через вершину i
 
                            if ((c[CurVertex, i] - f[CurVertex, i] < Flow[CurVertex]))
                                Flow[i] = c[CurVertex,i];
                           else
                                Flow[i] = Flow[CurVertex];
                        }
 
                    }
                QP++;// прерходим к следующей в очереди вершине
            }
 
            // закончив поиск пути
            if (Link[target] == -1) return 0; // мы или не находим путь и выходим
            // или находим:
            // тогда Flow[target] будет равен потоку который "дотек" по данному пути из истока в сток
            // тогда изменяем значения массива f для  данного пути на величину Flow[target]
            CurVertex = target;
            while (CurVertex != source) // путь из стока в исток мы восстанавливаем с помощбю массива Link
            {
                //if ((f[Link[CurVertex], CurVertex] + Flow[target]) > c[Link[CurVertex], CurVertex])
                {
                    //f[CurVertex,Link[CurVertex]] -= Flow[target];
                   // if (f[Link[CurVertex], CurVertex] + Flow[target] <= c[Link[CurVertex], CurVertex])
                   // {
                        f[Link[CurVertex], CurVertex] += Flow[target];
                   // }
                        CurVertex = Link[CurVertex];
                    
                    
                }
            }
            return Flow[target]; // Возвращаем значение потока которое мы еще смогли "пустить" по графу
        }
       
  
 
 
        public void DrawFlow(TextBox textBox1, Graphics graphic, PictureBox pbox, int[,] Items, List<Graph> Item)
        {
 
            Brush brush = new SolidBrush(Color.Red);
            Pen penelips = new Pen(brush);
 
            Font font = new Font("Arial", 12);
            graphic = pbox.CreateGraphics();
            // proverka(Items, f, Convert.ToInt16(textBox1.Text));
            for (int i = 0; i < Convert.ToInt16(textBox1.Text); i++)
            {
                for (int j = 0; j < Convert.ToInt16(textBox1.Text); j++)
                {
                    if ((Items[i, j] != 0) && (i != j) && (f[i, j]) != 0)
                    {
                        graphic.DrawString(Items[i, j].ToString() + "/" + f[i, j].ToString(), font, brush, new Point((Item[i].Locate.X + Item[j].Locate.X) / 2 - 4,
                            (Item[i].Locate.Y + Item[j].Locate.Y) / 2 - 4));
 
                    }
                    if (Items[i, j] != 0 && i != j)
                    {
                        graphic.DrawString(Items[i, j].ToString(), font, brush, new Point((Item[i].Locate.X + Item[j].Locate.X) / 2 - 4,
                                                  (Item[i].Locate.Y + Item[j].Locate.Y) / 2 - 4));
                    }
                }
            }
 
        }
 
        public int MaxFlow(int source, int target) // source - исток, target - сток
        {
            // инициализируем переменные:
            //memset(f, 0, sizeof(int) * MAX_VERTICES * MAX_VERTICES); // по графу ничего не течет
            Array.Clear(f, 0, f.Length);
            int MaxFlow = 0; // начальное значение потока
            int AddFlow;
            do
            {
                // каждую итерацию ищем какй-либо простой путь из истока в сток
                // и какой еще поток мажет быть пущен по этому пути
                AddFlow = FindPath(source, target - 1);
                MaxFlow += AddFlow;
            }
            while (AddFlow > 0);// повторяем цикл пока поток увеличивается
 
            return MaxFlow;
        }
 
 
        
    }
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
11.01.2015, 17:03
Ответы с готовыми решениями:

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

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

Алгоритм Форда-Фалкерсона. Нахождение максимального потока сети
В одном из городов имеется производство обуви на экспорт. Вся обувь отправляется диллерам морским путем через один и тот же порт. Для...

1
Warrior
 Аватар для _exp10der_
500 / 427 / 177
Регистрация: 23.11.2014
Сообщений: 932
11.01.2015, 17:20
https://kunuk.wordpress.com/20... le-with-c/
https://www.google.ru/search?q... ywOthIHgAg

вот мб поможет
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
11.01.2015, 17:20
Помогаю со студенческими работами здесь

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

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

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

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

Алгоритм Форда-Фалкерсона, программа выводит ноль
в чем проблема?вроде матрица инициализируется раз выводит первоначальную матрицу это алгоритм форда-фалкерсона. #include &lt;iostream&gt;...


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

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

Новые блоги и статьи
Компиляция 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. В течение многих лет мы сражались с замыканиями, диспетчеризацией очередей и обратными вызовами, чтобы. . .
Колмогоровская сложность: Приёмы упрощения кода
ArchitectMsa 20.03.2025
Наверное, каждый программист хотя бы раз сталкивался с кодом, который напоминает запутанный лабиринт — чем дальше в него погружаешься, тем сложнее найти выход. И когда мы говорим о сложности кода, мы. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru