Algoritmo de Floyd-Warshall | pseudocodigo

Pseudocodigo

Convenientemente, cuando calculamos el k-esimo caso, se puede sobreescribir la información salvada en la computación k -1. Esto significa que el algoritmo usa memoria cuadrática. Hay que cuidar la inicialización de las condiciones:

1 /* Suponemos que la función pesoArista devuelve el coste del camino que va de i a j
2    (infinito si no existe).
3 También suponemos que  es el número de vértices y pesoArista(i,i) = 0
4 */
5
6 int camino[][];
7 /* Una matriz bidimensional. En cada paso del algoritmo, camino[i][j] es el camino mínimo 
8 de i hasta j usando valores intermedios de (1..k-1). Cada camino[i][j] es inicializado a 
9
10 */
11
12 procedimiento FloydWarshall ()
13    para k: = 0 hasta n − 1
14
15          camino[i][j] = mín ( camino[i][j], camino[i][k]+camino[k][j])
16
17    fin para
Other Languages