Flujo máximo: ejemplo de código de algoritmo de Ford Fulkerson

Este equipo de redactores ha estado mucho tiempo buscando la respuesta a tus dudas, te brindamos la respuestas de modo que nuestro deseo es servirte de mucha ayuda.

Ejemplo: flujo máximo de ford fulkerson

// C++ program for implementation of Ford Fulkerson// algorithm#include#include#include#includeusingnamespace std;// Number of vertices in given graph#defineV6/* Returns true if there is a path from source 's' to sink
  't' in residual graph. Also fills parent[] to store the
  path */boolbfs(int rGraph[V][V],int s,int t,int parent[])// Create a visited array and mark all vertices as not// visitedbool visited[V];memset(visited,0,sizeof(visited));// Create a queue, enqueue source vertex and mark source// vertex as visited
    queue<int> q;
    q.push(s);
    visited[s]=true;
    parent[s]=-1;// Standard BFS Loopwhile(!q.empty())int u = q.front();
        q.pop();for(int v =0; v < V; v++)if(visited[v]==false&& rGraph[u][v]>0)// If we find a connection to the sink node,// then there is no point in BFS anymore We// just have to set its parent and can return// trueif(v == t)
                    parent[v]= u;returntrue;
                q.push(v);
                parent[v]= u;
                visited[v]=true;// We didn't reach sink in BFS starting from source, so// return falsereturnfalse;// Returns the maximum flow from s to t in the given graphintfordFulkerson(int graph[V][V],int s,int t)int u, v;// Create a residual graph and fill the residual graph// with given capacities in the original graph as// residual capacities in residual graphint rGraph[V][V];// Residual graph where rGraph[i][j]// indicates residual capacity of edge// from i to j (if there is an edge. If// rGraph[i][j] is 0, then there is not)for(u =0; u < V; u++)for(v =0; v < V; v++)
            rGraph[u][v]= graph[u][v];int parent[V];// This array is filled by BFS and to// store pathint max_flow =0;// There is no flow initially// Augment the flow while tere is path from source to// sinkwhile(bfs(rGraph, s, t, parent))// Find minimum residual capacity of the edges along// the path filled by BFS. Or we can say find the// maximum flow through the path found.int path_flow = INT_MAX;for(v = t; v != s; v = parent[v])
            u = parent[v];
            path_flow =min(path_flow, rGraph[u][v]);// update residual capacities of the edges and// reverse edges along the pathfor(v = t; v != s; v = parent[v])
            u = parent[v];
            rGraph[u][v]-= path_flow;
            rGraph[v][u]+= path_flow;// Add path flow to overall flow
        max_flow += path_flow;// Return the overall flowreturn max_flow;// Driver program to test above functionsintmain()// Let us create a graph shown in the above exampleint graph[V][V]=0,16,13,0,0,0,0,0,10,12,0,0,0,4,0,0,14,0,0,0,9,0,0,20,0,0,0,7,0,4,0,0,0,0,0,0;
 
    cout <<"The maximum possible flow is "<<fordFulkerson(graph,0,5);return0;

Al final de la web puedes encontrar las interpretaciones de otros sys admins, tú además tienes la libertad de insertar el tuyo si lo crees conveniente.

---

---

Utiliza Nuestro Buscador