25 septiembre 2009

Floyd-Warshall

Después de mucho darle vueltas a un problema he descubierto cuál era el error. Escribí de cabeza el algoritmo de floyd-warshall y lo probé con un ejemplillo y funcionaba bien. Total, son 3 bucles y un if... Pues estaba mal.

Floyd-Warshall devuelve la matriz dist con la distancia mínima entre todas las parejas de nodos de un grafo.

Este es el algoritmo correcto:


for (k = 0; k < nnodes; k++) {
for (j = 0; j < nnodes; j++) {
for (i = 0; i < nnodes; i++) {
double d = dist[i][k] + dist[k][j];
if (d < dist[i][j])
dist[i][j] = d;
}
}
}


Yo había puesto el bucle exterior recorriendo la i y el interior la k y eso no da el resultado correcto.

En fin, he conseguido pasar al capítulo 3 de la USACO.