Advertisement
Guest User

Untitled

a guest
Nov 21st, 2017
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.21 KB | None | 0 0
  1.     public int distanciaMasCorta(int origen, int destino) {
  2.         int[] dist = new int[tope];
  3.         boolean[] vis = new boolean[tope];
  4.         int[] ant = new int[tope];
  5.         for(int i = 0; i < tope; i++) {
  6.             dist[i] = Integer.MAX_VALUE;
  7.             ant[i] = -1;
  8.         }
  9.        
  10.         dist[origen] = 0;
  11.         vis[origen] = true;
  12.         for(int i = 0; i < tope; i++) {
  13.             if(matAdy[origen][i].isExiste()) {
  14.                 dist[i] = matAdy[origen][i].getPeso();
  15.                 ant[i] = origen;
  16.             }
  17.         }
  18.        
  19.         for(int k = 1; k < tope; k++) {
  20.             int min = Integer.MAX_VALUE;
  21.             int cand = -1;
  22.             for(int i = 0; i < tope; i++) {
  23.                 if(dist[i] < min && !vis[i]) {
  24.                     min = dist[i];
  25.                     cand = i;
  26.                 }
  27.             }
  28.        
  29.             if(cand == -1) {
  30.                 break;
  31.             }
  32.            
  33.             vis[cand] = true;
  34.             for(int i = 0; i < tope; i++) {
  35.                 int pasoFinal = matAdy[cand][i].getPeso();
  36.                 if(matAdy[cand][i].isExiste() && !vis[i] && dist[cand] + pasoFinal < dist[i]) {
  37.                     dist[i] = dist[cand] + pasoFinal;
  38.                     ant[i] = cand;
  39.                 }
  40.             }
  41.         }
  42.        
  43.         // No se encontro camino
  44.         if(dist[destino] == Integer.MAX_VALUE) {
  45.             return -1;
  46.         }
  47.        
  48.         return dist[destino];
  49.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement