Java - algortimo Dijkstra

   
Vista:

algortimo Dijkstra

Publicado por fernando correa (1 intervención) el 10/09/2008 17:56:44
hola laguna persona tiene el codigo en java del algoritmo de Dijsktra lo necesito urgente y la verdad no se copmo programarlo les agradeceria que si alguien lo tiene me pudiera hacer el favor de enviarme lo al mail fhernandovic@hotmail.com
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

RE:algortimo Dijkstra

Publicado por Karel (3 intervenciones) el 10/03/2009 23:17:34
// Algoritmos de el problema de caminos mínimos

public void Dijkstra(T v1, T[] antecesores, double[] costo) {
visitados = new boolean[vertices.Longitud()];
int pos = vertices.Buscar(v1);
costo[pos] = 0;
visitados[pos] = true;
for (int i = 0; i < costo.length; i++) {
if (matriz[pos][i] != -1) {
costo[i] = matriz[pos][i];
}else{
costo[i] = Double.MAX_VALUE;
}
antecesores[i] = v1;
}

while (NoVisitadosTodos()) {
int pm = MinimoNoVicitado(costo);
visitados[pm] = true;
for (int i = 0; i < visitados.length; i++) {
if (!visitados[i]) {
if (matriz[pm][i] != -1) {
if (costo[i] > costo[pm] + matriz[pm][i]) {
costo[i] = costo[pm] + matriz[pm][i];
antecesores[i] = vertices.Obtener(pm);
}
}
}
}
}
}

// Metodos Auxiliares

boolean NoVisitadosTodos() {
for (int i = 0; i < visitados.length; i++) {
if (!visitados[i]) {
return true;
}
}
return false;
}

int MinimoNoVicitado(double[] costo) {
double min = Double.MAX_VALUE;
int pos = 0;
for (int i = 0; i < costo.length; i++) {
if (!visitados[i]) {
double d = costo[i];
if (d <= min) {
min = d;
pos = i;
}
}
}
return pos;
}
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar