Форум программистов, компьютерный форум CyberForum.ru

Не работает алгоритм Форда-Фалкерсона - C++

Восстановить пароль Регистрация
 
The_Fat_Man
 Аватар для The_Fat_Man
9 / 9 / 3
Регистрация: 04.03.2014
Сообщений: 138
04.03.2014, 18:02     Не работает алгоритм Форда-Фалкерсона #1
Добрый день уважаемые форумчане! У меня проблема. Реализовал алгоритм Форда-Фалкерсона. Программа компилируется, но правильного результата не выдает. Переделывал ее уже два раза, но все тщетно, поэтому вы - моя последняя надежда.

Суть: На вход дан взвешенный ориентированный граф. Нужно найти величину max потока.

Начинаем программу, считывая файл data.txt:

5
0 5 4 4 0
-5 0 -1 0 2
-4 1 0 -1 4
-4 0 1 0 5
0 -2 -4 -5 0

-1 0 0 1 -1
0 -1 0 -1 0
0 0 -1 1 1
1 -1 1 -1 0
-1 0 1 0 -1

5 - Число вершин в графе

1-ая матрица - матрица пропускной способности, в которой [0] означает, что вершины не смежны, а отрицательное значение свидетельствует о том, что дуга обратная.

2-ая матрица - матрица нагрузки на сеть в настоящее время. [0] - вершины не смежны, "-" - обратная дуга.

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include<iostream>
#include<fstream>
#include <locale.h>
 
using namespace std;
 
int numVertex; // Число вершин в графе
int **inputMatrix; // Матрица пропускной способности
int **inputFlow; // Матрица NOW нагрузки
 
// ЗАВЕДЕМ МАССИВ rArr ВЕЛИЧИН ОСТАТОЧНОЙ ПРОПУСКНОЙ СПОСОБНОСТИ СЕТИ РАЗМЕРНОСТИ n+1=|V|
// В НЕМ БУДЕТ ХРАНИТЬСЯ ИНФОРМАЦИЯ О ПРОПУСКНОЙ СПОСОБНОСТИ УВЕЛИЧИВАЮЩЕГО ПУТИ
 
int *rArr = new int [numVertex];
 
// ЗАВЕДЕМ МАССИВ МЕТОК ВЕРШИН pArr РАЗМЕРНОСТИ n+1=|V|
// В НЕМ БУДЕТ ХРАНИТЬСЯ ИНФОРМАЦИЯ О ВЕРШИНАХ, ВХОДЯЩИХ В УВЕЛИЧИВАЮЩИЙ ПУТЬ
 
int *pArr = new int [numVertex];
 
// ЗАВЕДЕМ МАССИВ МЕТОК ЦВЕТА ВЕРШИН colArr РАЗМЕРНОСТИ n+1=|V|
// В НЕМ БУДЕТ ХРАНИТЬСЯ ИНФОРМАЦИЯ О ПОСЕЩЕННЫХ ИЛИ НЕПОСЕЩЕННЫХ ВЕРШИНАХ ПРИ ПОСТРОЕНИИ УВЕЛИЧИВАЮЩЕГО ПУТИ
 
int *colArr = new int [numVertex];
 
void iniFF()
{
    rArr[0]=1000; // Исток имеет бесконечную пропускную способность
    pArr[0]=0;    // Исток обязательно является началом увеличивающего пути
    colArr[0]=-1; // Вершина V0 изначально окрашивается в белый цвет
 
    for(int i=1; i<numVertex; i++)
    {
        rArr[i]=0;
        pArr[i]=-1;
        colArr[i]=-1;
    }
}
 
void Ford_Fulkerson()
{
    iniFF(); // Запускаем функцию инициализации
 
    int helper=0; // !!!!!!! КОСТЫЛЬ !!!!!!!!
 
    for(int tmp=0; tmp<numVertex; tmp++)
    {
        if(colArr[tmp]==-1 && pArr[tmp]!=-1)
        {
            // Сейчас действие для некоторой белой вершины с p[tmp]!=-1
            for(int i=0; i<numVertex; i++)
            {
                if(inputMatrix[tmp][i]!=0 && pArr[i]==-1) // !!!!!!!!!!?????? ТОЧНО ПРОВЕРЯЕМ ПО pArr, а не colArr !!!!!!!!!????????
                {
                    // Для каждой непомеченной вершины из окружения для tmp
                    if(inputMatrix[tmp][i]>0) // ПРЯМАЯ ДУГА
                        if(inputFlow[tmp][i]<inputMatrix[tmp][i])
                            {
                                    // Дуга прямая и f<c, где f - величина текущего (now), c - пропускная способность
                                    if(inputMatrix[tmp][i]<0)
                                        helper = (-1)*(inputMatrix[tmp][i]); // КОСТЫЛЬ
                                    else
                                        helper = inputMatrix[tmp][i];
 
                                    rArr[i] = helper - inputFlow[tmp][i];
                                    pArr[i] = tmp;
                                }
 
                            if(inputMatrix[tmp][i]<0) // ОБРАТНАЯ ДУГА
                                if(inputFlow[tmp][i]>0)
                                {
                                    rArr[i] = inputFlow[tmp][i];
                                    pArr[i] = tmp;
                                }
 
 
                        colArr[tmp]=1;
                        if(pArr[numVertex-1]!=-1)
                        {
                            int cf = rArr[0];
                            for(int k=0; k<numVertex; k++)
                            {
                                if(cf>=rArr[i])
                                    cf = rArr[i];
                            }
 
                            for(int k=0; k<numVertex; k++)
                            {
                                if(inputMatrix[i][k]!=0)
                                {
                                    if(inputMatrix[i][k]>0) /////// ????????????????????
                                        inputFlow[i][k] = inputFlow[i][k] + cf;
                                    else
                                        inputFlow[i][k] = inputFlow[i][k] - cf;
                                }
                            }
 
                            iniFF();
                        }
                    }
                }
        }
    } // Конец главного цикла алгоритма
}
 
int main() {
    setlocale(LC_CTYPE,"Russian");
 
    ifstream fin("data.txt");
    if(!fin)
    {
        cout << "Не удалось открыть файл.\n";
        cin.get(); // Пауза в Code::Blocks без визуального оповещения
        return 1; // Возвращаем ошибку
    }
 
    fin >> numVertex; // Считываем число вершин (первое число в файле)
 
    inputMatrix = new int* [numVertex];
    for(int i=0; i<numVertex; i++)
        inputMatrix[i] = new int [numVertex];
 
    inputFlow = new int* [numVertex];
    for(int i=0; i<numVertex; i++)
        inputFlow[i] = new int [numVertex];
 
    for(int i=0; i<numVertex; i++)
    {
        for(int j=0; j<numVertex; j++)
            fin >> inputMatrix[i][j];
    }
 
    for(int i=0; i<numVertex; i++)
    {
        for(int j=0; j<numVertex; j++)
            fin >> inputFlow[i][j];
    }
 
    cout << "Вывод входных данных.\n" << "Матрица, содержащая MAX проводимость труб:\n\n";
 
    for(int i=0; i<numVertex; i++)
    {
        for(int j=0; j<numVertex; j++)
            cout << inputMatrix[i][j] << " ";
        cout << endl;
    }
 
    cout << "\nМатрица, показывающая первоначальную нагрузку на сеть:\n"
    << "[-1] означает, что НЕТ проводимости из i-ой в j-тую вершину.\n\n";
 
    for(int i=0; i<numVertex; i++)
    {
        for(int j=0; j<numVertex; j++)
            cout << inputFlow[i][j] << " ";
        cout << endl;
    }
 
    /////////////////////////////////////
    ///////////////////////////////////////
    ////////////////////////////////////////
 
    int sum=0;
 
    for(int n=0; n<numVertex; n++)
    {
        for(int y=0; y<numVertex; y++)
        {
            if(inputMatrix[n][y]!=0)
            {
                if(colArr[n]==-1)
                {
                    if(colArr[y]==1)
                    {
                        sum+=inputFlow[n][y];
                    }
                }
            }
 
            if(inputMatrix[n][y]!=0)
            {
                if(colArr[n]==1)
                {
                    if(colArr[y]==-1)
                    {
                        sum+=inputFlow[n][y];
                    }
                }
            }
        }
    }
 
    cout << "\nСуммарный поточек: " << sum << endl;
 
// ОЧИСТКА ВЫДЕЛЕННОЙ ПАМЯТИ
 
    /*
    for (int i=0; i<numVertex; i++)
        delete [] inputMatrix[i];
 
    for (int i=0; i<numVertex; i++)
        delete [] inputFlow[i];
    */
 
    /* КОМПИЛЯТОР РУГАЕТСЯ
    delete [] rArr;
    delete [] pArr;
    delete [] colArr;
    */
 
    return 0;
}
Ответ: Суммарный поток должен равняться 10.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.03.2014, 18:02     Не работает алгоритм Форда-Фалкерсона
Посмотрите здесь:

Алгоритм Форда-Беллмана C++
Алгоритм Форда - Беллмана C++
C++ Алгоритм Форда-Белмана
C++ Матрица Форда Беллмана и метод Дейкстра
Входные данные. Метод Форда-Фалкерсона C++
C++ Как работает алгоритм Khazad
C++ Алгоритм Форда-Беллмана
C++ Не работает алгоритм нахождения слов

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 14:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru