Hola.
Estoy desarrollando un código que encuentre el camino mas corto de un punto a otro en una matriz de peso, ya tengo el programa sólo que es de una matriz de adyacencia, la diferencia radica que en el de adyacencia al 'avanzar' siempre el valor es 1, y en una matriz de peso, hay distancias, puede ser que de 'a' a 'b' sea 10, y de 'b' a 'c' sea 5 por ejemplo. El código como pueden ver ya está terminado, sólo me gustaría que me hecharan una mano para modificar eso, o alguna idea no vendría nada mal.
Código Java:
Ver originalimport java.io.*;
//Declaración de la clase
public class Prim
{
{
int n,inicio,termino;
int [][]matriz;
// Se pide el orden de la matriz de adyacencia.
System.
out.
print("Ingrese el orden de la matriz de adyacencia : "); n
= Integer.
parseInt(lectura.
readLine()); // Se genera la matriz..
matriz = new int[n][n];
// Se piden los datos para la matriz.
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
System.
out.
print("Ingrese elemento ("+i
+","+j
+") : "); matriz
[i
][j
] = Integer.
parseInt(lectura.
readLine()); }
System.
out.
println("\n\nMatriz de Adyacencia : \n"); // Se pide indefinidamente nodos para ver su factibilidad.
// El ciclo sale con
do
{
// Se muestra la matriz.
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
System.
out.
print(" "+matriz
[i
][j
]); }
}
// Se piden los nodos a analizar.
System.
out.
print("Ingrese Nodo de Inicio : "); inicio
= Integer.
parseInt(lectura.
readLine()); System.
out.
print("Ingrese Nodo de Término : "); termino
= Integer.
parseInt(lectura.
readLine()); // Se verifica que los indices sean mayores o iguales a 0.
if((inicio >= 0)&&(termino>=0))
encontrarCaminoMasCorto(matriz,inicio,termino);
} while((inicio!=-1)&&(termino!=-1));
}
// Método que encuentra el camino mas corto entre 2
// vértices del grafo.
public static void encontrarCaminoMasCorto(int [][]m,int ini,int fin)
{
// Se verifica que no se este tratando de accesar a un vértice
// fuera del rango de la matriz de adyacencia.
if((ini>m.length-1)||(fin>m[0].length))
{
System.
out.
print("Indices fuera de rango..."); return;
}
// Se quiere ver el camino más corto desde un nodo a sí mismo
// entonces se imprime el coste de llegar a sí mismo.
if( ini == fin )
{
System.
out.
println("\t\t Costo de llegar de "+ini
+" a "+fin
+" es de "+m
[ini
][fin
]); return;
}
// Como los indices están bien ingresados y no se está
// tratando con el caso base de que se quiera llegar al mismo nodo
// entonces se busca la distancia más corta que hay entre el nodo "ini"
// y el nodo "fin".
System.
out.
println("\n\t\t Costo de llegar de "+ini
+" a "+fin
+" es de "+MostrarCaminoMasCorto
(ini,fin,ini,
0,m
)); }
// Método que muestra el camino más corto entre dos vértices del grafo.
public static int MostrarCaminoMasCorto(int ini,int ter,int x,int suma,int [][]matriz)
{
int i,j,garage;
// Si se pasarón los límites de orden de la matriz entonces
// quiere decir que el camino no se encuentra y se retorna 0.
if(x>(matriz.length-1))
{
System.
out.
print("El camino entre los nodos no existe..."); return -1;
}
// Como se esta todavía dentro de la matriz entonces se
// sigue buscando un nodo que llegue al nodo terminal.
for(i=0;i<matriz[0].length;i++)
{
// Existe una llegada al nodo deseado entonces
// Se suma el costo al costo general y se retorna la suma.
if(matriz[x][ter]!=0)
{
System.
out.
println("Revisando Nodo "+x
+" - Costo : "+suma
); suma += matriz[x][ter];
break;
}
else
// Como lo anterior no pasó entonces se verifica que
// existe un camino para pasar al próximo nivel.
if(matriz[x][i]!=0) // Camino existe
{
System.
out.
println("Revisando Nodo "+x
+" - Costo : "+suma
); garage = suma;
suma += MostrarCaminoMasCorto(ini,ter,x+1,suma,matriz);
if(suma==-1)
suma = garage;
else
if((suma>garage)&&(garage!=0))
suma=garage;
}
}
return suma;
}
}// Fin de la clase
De antemano, muchas gracias.
Saludos.