Foros del Web » Programación para mayores de 30 ;) » Java »

Dudas con parametros para este método

Estas en el tema de Dudas con parametros para este método en el foro de Java en Foros del Web. Buenas, necesito hacer funcionar el Algoritmo de Edmonds-Karp que encuentra el Flujo Maximo de un Grafo. Si bien me conseguí la implementacion en Java, pero ...
  #1 (permalink)  
Antiguo 02/07/2011, 21:00
 
Fecha de Ingreso: junio-2009
Mensajes: 84
Antigüedad: 14 años, 9 meses
Puntos: 2
Dudas con parametros para este método

Buenas, necesito hacer funcionar el Algoritmo de Edmonds-Karp que encuentra el Flujo Maximo de un Grafo. Si bien me conseguí la implementacion en Java, pero me hace falta entender que parametros exactamente me pide el método.
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 PHP:
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[][] Eint[][] Cint sint t) {
        
int n C.length;
        
// Residual capacity from u to v is C[u][v] - F[u][v]
        
int[][] = new int[n][n];
        while (
true) {
            
int[] = new int[n]; // Parent table
            
Arrays.fill(P, -1);
            
P[s] = s;
            
int[] = new int[n]; // Capacity of path to node
            
M[s] = Integer.MAX_VALUE;
            
// BFS queue
            
Queue<Integer= 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] > && P[v] == -1) {
                        
P[v] = u;
                        
M[v] = Math.min(M[u], C[u][v] - F[u][v]);
                        if (
!= t)
                            
Q.offer(v);
                        else {
                            
// Backtrack search, and write flow
                            
while (P[v] != v) {
                                
P[v];
                                
F[u][v] += M[t];
                                
F[v][u] -= M[t];
                                
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;
            }
        }
    }


Fuente del algoritmo:
[URL="http://en.wikibooks.org/wiki/Algorithm_Implementation/Graphs/Maximum_flow/Edmonds-Karp"]http://en.wikibooks.org/wiki/Algorithm_Implementation/Graphs/Maximum_flow/Edmonds-Karp[/URL]

Última edición por Gaudy; 02/07/2011 a las 21:15

Etiquetas: dudas, parametros
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 03:48.