Skip to content
TheChatArchiveThe Chat Archive
gpt-4-1106-preview· OpenAIHugging Face Arena Human Preference 55K

Write max flow algorithm of your choice in C++

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with gpt-3.5-turbo-1106’s answer.
  1. User

    Write max flow algorithm of your choice in C++

  2. Assistant

    Certainly! Below is a basic implementation of the Edmonds-Karp algorithm in C++, which is an implementation of the Ford-Fulkerson method for computing the maximum flow in a flow network. The algorithm uses breadth-first search (BFS) to find the shortest augmenting path.

    #include <iostream>
    #include <vector>
    #include <queue>
    #include <climits>
    
    using namespace std;
    
    // Number of vertices in the graph
    #define V 6
    
    // Using BFS as a searching algorithm to find path from source to sink.
    // Returns true if there is a path from source 's' to sink 't' in residual graph.
    // Also, fills parent[] to store the path.
    bool bfs(int rGraph[V][V], int s, int t, int parent[]) {
        // Create a visited array and mark all vertices as not visited
        vector<bool> visited(V, false);
    
        // 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 Loop
        while (!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
                    if (v == t) {
                        parent[v] = u;
                        return true;
                    }
                    q.push(v);
                    parent[v] = u;
                    visited[v] = true;
                }
            }
        }
    
        // We didn't reach sink in BFS starting from source, so return false
        return false;
    }
    
    // Returns the maximum flow from s to t in the given graph
    int edmondsKarp(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 graph
        int 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 path
    
        int max_flow = 0;  // There is no flow initially
    
        // Augment the flow while there is path from source to sink
        while (bfs(rGraph, s, t, parent)) {
            // Find the minimum residual capacity of the edges along the path filled by BFS.
            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 path
            for (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 flow
        return max_flow;
    }
    
    int main() {
        // Let us create a graph shown in the above example
        int 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 " << edmondsKarp(graph, 0, 5);
    
        return 0;
    }
    

    This program defines a graph using a 2D array, where graph[u][v] represents the capacity of the edge from u to v. The edmondsKarp function calculates the maximum flow from source s to sink t in the provided graph and prints the result.

    To compile and run this program, you can use a C++ compiler like g++. Save the code to a file, for example, max_flow.cpp, and then use the

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.