Saltar al contenido

ejemplo de código de código de flujo máximo de ford fulkerson

Basta ya de buscar en internet porque llegaste al sitio necesario, poseemos la solución que quieres recibir pero sin problema.

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;

Si estás contento con lo expuesto, tienes la opción de dejar un escrito acerca de qué te ha parecido este ensayo.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *