Skip to main content
3 de 10
se eliminaron 12 caracteres en el cuerpo
Alex Rivas
  • 496
  • 4
  • 21

Aqui tienes el codigo. Si estas familiarizado con ese algoritmo lo que hace es devuelve una matriz con las distancias mínimas de cada nodo al resto de los vértices.

Su tiempo es muy de ejecucion es muy grande es de O( V^3 ) por tanto para mas de mil el programa deja de ser util.

Debes inicializar el arreglo path en 0 para cada cuidad. Lo haces con un for asi:

for(int i = 0; i < cn; i++)
    path[i][i] = 0;

for(int k = 0; k < cn; k++)
    for(int i = 0; i < cn; i++)
        for(int j = 0; j < cn; j++){
            int dt = path[i][k] + path[k][j];
            if(path[i][j] > dt)
                path[i][j] = dt;

Luego para saber la distancia minima de i a j simplemente llama al arreglo en path[i][j]. Espero que haya sido de ayuda.

Guiate por el de arriba seria algo asi Primero que nada crea un arreglo llamado path e inicializalo de la siguiente forma

cn = cantidad de nodos

 for(int i = 0; i < cn; i++)
        path[origen[i]][destino[i]] = distancia[i];

for(int i = 0; i < cn; i++)
    path[i][i] = 0;

for(int k = 0; k < cn; k++)
    for(int i = 0; i < cn; i++)
        for(int j = 0; j < cn; j++){
            int dt = path[i][k] + path[k][j];
            if(path[i][j] > dt)
                path[i][j] = dt;
Alex Rivas
  • 496
  • 4
  • 21