Manquer quelques chemins dans l'algorithme de flux d'Edmonds Karp

Question

Je mettrais en œuvre Algorithme d'Edmond Karp, mais il semble que ce ne soit pas correct et je n'obtiens pas de flux correct, envisagez de suivre le graphique et le flux de 4 à 8:

L'algorithme fonctionne comme suit:

Trouve d'abord 4 → 1 → 8, puis trouve 4 → 5 → 8 après cela 4 → 1 → 6 → 8

Et je pense que le troisième chemin est mauvais, car en utilisant ce chemin, nous ne pouvons pas utiliser le flux de 6 → 8 (car il est utilisé), et en fait nous ne pouvons pas utiliser le flux de 4 → 5 → 6 → 8.

En fait, si nous choisissons 4 → 5 → 6 → 8, puis 4 → 1 → 3 → 7 → 8 puis 4 → 1 → 3 → 7 → 8, nous pouvons gagner un meilleur écoulement (40).

J'ai implémenté un algorithme à partir d'un exemple de code Wiki. Je pense que nous ne pouvons pas utiliser de chemin valide et, en fait, cette sélection gourmand est mauvaise.

Ai-je tort?

Le code est comme ci-dessous (en C #, le seuil est 0 et n'affecte pas l'algorithme):

   public decimal EdmondKarps(decimal[][] capacities/*Capacity matrix*/,
                    List<int>[] neighbors/*Neighbour lists*/,
                    int s /*source*/,
                    int t/*sink*/,
                    decimal threshold,
                    out decimal[][] flowMatrix
                    /*flowMatrix (A matrix giving a legal flowMatrix with the maximum value)*/
                    )
    {
        THRESHOLD = threshold;
        int n = capacities.Length;
        decimal flow = 0m; // (Initial flowMatrix is zero)
        flowMatrix = new decimal[n][]; //array(1..n, 1..n) (Residual capacity from u to v is capacities[u,v] - flowMatrix[u,v])
        for (int i = 0; i < n; i++)
        {
            flowMatrix[i] = new decimal[n];
        }

        while (true)
        {
            var path = new int[n];
            var pathCapacity = BreadthFirstSearch(capacities, neighbors, s, t, flowMatrix, out path);
            if (pathCapacity <= threshold)
                break;
            flow += pathCapacity;

            //(Backtrack search, and update flowMatrix)
            var v = t;
            while (v != s)
            {
                var u = path[v];
                flowMatrix[u][v] = flowMatrix[u][v] + pathCapacity;
                flowMatrix[v][u] = flowMatrix[v][u] - pathCapacity;
                v = u;
            }
        }
        return flow;
    }

    private decimal BreadthFirstSearch(decimal[][] capacities, List<int>[] neighbors, int s, int t, decimal[][] flowMatrix, out int[] path)
    {
        var n = capacities.Length;
        path = Enumerable.Range(0, n).Select(x => -1).ToArray();//array(1..n)
        path[s] = -2;
        var pathFlow = new decimal[n];
        pathFlow[s] = Decimal.MaxValue; // INFINT
        var Q = new Queue<int>(); // Q is exactly Queue :)
        Q.Enqueue(s);
        while (Q.Count > 0)
        {
            var u = Q.Dequeue();
            for (int i = 0; i < neighbors[u].Count; i++)
            {
                var v = neighbors[u][i];
                //(If there is available capacity, and v is not seen before in search)
                if (capacities[u][v] - flowMatrix[u][v] > THRESHOLD && path[v] == -1)
                {
                    // save path:
                    path[v] = u;
                    pathFlow[v] = Math.Min(pathFlow[u], capacities[u][v] - flowMatrix[u][v]);
                    if (v != t)
                        Q.Enqueue(v);
                    else
                        return pathFlow[t];
                }
            }
        }
        return 0;
    }

Answer 1

La façon de choisir les chemins n'est pas importante.

Vous devez ajouter des bords du chemin dans l'ordre inverse avec la capacité du chemin et réduire la capacité des bords du chemin par cette valeur.

En fait, cette solution fonctionne:

while there is a path with positive capacity from source to sink{
    find any path with positive capacity from source to sink, named P with capacity C.
    add C to maximum_flow_value.
    reduce C from capacity of edges of P.
    add C to capacity of edges of reverse_P.
}

Enfin, la valeur de l'écoulement maximal est la somme de Cs dans la boucle.

Si vous voulez voir le flux dans les bords dans le flux maximum que vous avez fait, vous pouvez conserver le graphique initial quelque part, le flux dans le bord E serait original_capacity_e - current_capacity_e.