Por cierto:
C: es la matriz de representacion del Grafo
E: ?
s: nodo de inicio
t: nodo destino
Mi dudas son:
Si fuera posible que alguien me explicara que es el E, se q es una matriz, pero no se de que. En el parametro me piden los nodos s y t, pero en ¿¿formato int??
Código
import java.util.*; /** * Finds the maximum flow in a flow network. * @param E neighbour lists * @param C capacity matrix (must be n by n) * @param s source * @param t sink * @return maximum flow */ public class EdmondsKarp { public static int edmondsKarp(int[][] E, int[][] C, int s, int t) { int n = C.length; // Residual capacity from u to v is C[u][v] - F[u][v] int[][] F = new int[n][n]; while (true) { int[] P = new int[n]; // Parent table P[s] = s; int[] M = new int[n]; // Capacity of path to node // BFS queue Queue<Integer> Q = new LinkedList<Integer>(); Q.offer(s); LOOP: while (!Q.isEmpty()) { int u = Q.poll(); for (int v : E[u]) { // There is available capacity, // and v is not seen before in search if (C[u][v] - F[u][v] > 0 && P[v] == -1) { P[v] = u; if (v != t) Q.offer(v); else { // Backtrack search, and write flow while (P[v] != v) { u = P[v]; F[u][v] += M[t]; F[v][u] -= M[t]; v = u; } break LOOP; } } } } if (P[t] == -1) { // We did not find a path to t int sum = 0; for (int x : F[s]) sum += x; return sum; } } } }