Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public int distanciaMasCorta(int origen, int destino) {
- int[] dist = new int[tope];
- boolean[] vis = new boolean[tope];
- int[] ant = new int[tope];
- for(int i = 0; i < tope; i++) {
- dist[i] = Integer.MAX_VALUE;
- ant[i] = -1;
- }
- dist[origen] = 0;
- vis[origen] = true;
- for(int i = 0; i < tope; i++) {
- if(matAdy[origen][i].isExiste()) {
- dist[i] = matAdy[origen][i].getPeso();
- ant[i] = origen;
- }
- }
- for(int k = 1; k < tope; k++) {
- int min = Integer.MAX_VALUE;
- int cand = -1;
- for(int i = 0; i < tope; i++) {
- if(dist[i] < min && !vis[i]) {
- min = dist[i];
- cand = i;
- }
- }
- if(cand == -1) {
- break;
- }
- vis[cand] = true;
- for(int i = 0; i < tope; i++) {
- int pasoFinal = matAdy[cand][i].getPeso();
- if(matAdy[cand][i].isExiste() && !vis[i] && dist[cand] + pasoFinal < dist[i]) {
- dist[i] = dist[cand] + pasoFinal;
- ant[i] = cand;
- }
- }
- }
- // No se encontro camino
- if(dist[destino] == Integer.MAX_VALUE) {
- return -1;
- }
- return dist[destino];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement