Solving Max Flow Problem: Find Zero Output?

  • Thread starter datuna
  • Start date
  • Tags
    Flow Max
In summary, the code is not functioning properly because the parent array has not been initialized, leading to incorrect output. Initialize the parent array with -1 before calling the reachable() function.
  • #1
datuna
1
0
i have following code
Code:
#include<iostream>
#define MAX 100
using namespace std;
int graph[MAX][MAX];
int queue[MAX];
int head,tail;
int parent[MAX];
int V,E;
int s,t,fTotal;
int F[MAX][MAX];

//breadth First search
bool reachable(int s,int  t){
    bool found=false;
    head=tail=0;
    int vq;
    memset(parent,255,sizeof(parent));
    queue[tail++]=s;
    parent[s]=s;
    while(head< tail && ! found){
        vq=queue[head++];
        for(int i=0;i<V;i++){
            //Parents also made the function as visit vector
            if(graph[vq][i] && parent[i]==-1)
                queue[tail++]=i;
            parent[i]=vq;
            if(i==t){
                found=true;
                break;
            }
        }
    }
    return found;
}

void maxflow(){
    int vj,min;
    fTotal=0;
    while(reachable(s,t)){
        //Gets the minimum possible capacity in edges of the path s to t
        min=graph[parent[t]][t];
        vj=t;
        while(parent[vj]!=vj){
            if(graph[parent[vj]][vj]<min)
                min=graph[parent[vj]][vj];
            vj=parent[vj];
        }

        vj=t;
        while(parent[vj]!=vj){

            graph[parent[vj]][vj]-=min;
            graph[vj][parent[vj]]+=min;
            F[parent[vj]][vj]+=min;
            vj=parent[vj];
        }
        fTotal+=min;
    }
}

bool read(){
    cin>>V>>E>>s>>t;
    if(!V && !E) return false;
    memset(graph,0,sizeof(graph));
    memset(queue,0,sizeof(queue));
    memset(F,0,sizeof(F));
    int v1,v2,val;
    for(int i=0;i<E;i++){
        cin>>v1>>v2>>val;
        graph[v1][v2]=val;
    }
    return true;
}

int  main(){
    while(read()){
        maxflow();
        cout<<" max flow from s to t is : "<<fTotal<<endl;
    }
    return 0;
}
which for this input

(1,2) 2
(1,3) 3
(2,4) 3
(3,4) 1
(2,5) 1
(3,5) 1
(4,6) 2
(5,6) 3
returns zero as output,please tell me what is wrong?
 
Last edited by a moderator:
Technology news on Phys.org
  • #2
The problem is that you have not initialized the parent array. You have only declared it. Initialize the parent array with -1 before calling reachable() function.
 

Q1: What is the Max Flow Problem?

The Max Flow Problem is a mathematical optimization problem that involves finding the maximum flow that can be sent through a network from a given source to a given sink. This problem is commonly used in transportation, communication, and production planning.

Q2: What is the significance of finding Zero Output in the Max Flow Problem?

Finding Zero Output in the Max Flow Problem means that there is no flow from the source to the sink, indicating that the network is unable to fulfill the desired demand. This could be due to capacity constraints or blockages in the network.

Q3: How is the Max Flow Problem solved?

The Max Flow Problem can be solved using various algorithms, such as the Ford-Fulkerson method, the Edmonds-Karp algorithm, or the Dinic's algorithm. These algorithms use different approaches, such as augmenting paths or residual networks, to find the maximum flow in the network.

Q4: What is the role of the Zero Output in the solution of the Max Flow Problem?

The Zero Output serves as a stopping condition in the algorithms used to solve the Max Flow Problem. Once Zero Output is reached, the algorithm stops and provides the maximum flow value. If the Zero Output is not reached, the algorithm continues to find an optimal solution.

Q5: Can the Max Flow Problem be applied in real-life situations?

Yes, the Max Flow Problem has various real-life applications, such as optimizing traffic flow, planning airline schedules, and designing telecommunication networks. It is a useful tool for decision-making and resource allocation in various industries.

Similar threads

  • Programming and Computer Science
Replies
1
Views
1K
Replies
10
Views
951
  • Programming and Computer Science
3
Replies
75
Views
4K
  • Programming and Computer Science
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Programming and Computer Science
Replies
33
Views
6K
  • Programming and Computer Science
Replies
15
Views
3K
  • Programming and Computer Science
Replies
8
Views
2K
  • Programming and Computer Science
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
Back
Top