Estructuras de datos
Publicado por Alberto (1 intervención) el 24/01/2018 21:41:51
He estado haciendo el algoritmo de dijkstra, y consigue que me muestre las distancias mas cortas desde un vertice de origen a todos lo demas.
Y ahora quiero guardar los caminos para llegar a esos vertices, por favor si alguien me puede ayidar.
Y ahora quiero guardar los caminos para llegar a esos vertices, por favor si alguien me puede ayidar.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static int[] calcular(int origen, int[][] matriz) {
int vertices = matriz.length;
boolean[] vistos = new boolean[vertices];
int[] distancias = new int[vertices];
String[] caminos = new String[vertices];
for(int i = 0; i < vertices; i++ )
caminos[i] = origen+" ";
for(int i = 0; i < vertices; i++) {
distancias[i] = Integer.MAX_VALUE;
vistos[i] = false;
previo[i] = -1;
}distancias[origen] = 0;
int v;
for(int i = 0; i < vertices; i++) {
v = buscarMinVertice(distancias, vistos);
vistos[v] = true;
for(int j = 0; j < vertices; j++)
if(matriz[v][j] != 0 && !vistos[j] && distancias[v] != Integer.MAX_VALUE)
if(distancias[v] + matriz[v][j] < distancias[j])
distancias[j] = distancias[v] + matriz[v][j];
}return distancias;
}private static int buscarMinVertice(int[] distancias, boolean[] vistos) {
int minVertice = -1;
for(int i = 0; i < distancias.length; i++)
if(!vistos[i] && (minVertice == -1 || distancias[i] < distancias[minVertice]))
minVertice = i;return minVertice;
}Valora esta pregunta
0