Optimice Floyd-Warshall para la matriz de adyacencia simétrica

Question

¿Existe una optimización que reduzca el factor constante del tiempo de ejecución de Floyd-Warshall, si se garantiza que tiene una matriz de adyacencia simétrica?

Answer 1

Después de pensarlo se me ocurrió:

for (int k = 0; k < N; ++k) 
    for (int i = 0; i < N; ++i) 
     for (int j = 0; j <= i; ++j) 
      dist[j][i] = dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); 

Ahora, por supuesto que ambos tienen que mostrar que es correcto y rápido.

La corrección es más difícil de probar, ya que se basa en la prueba de Floyd-Warshall que no es trivial. Una buena prueba se da aquí: Floyd-Warshall proof

La matriz de entrada es symmetric. Ahora el resto de la prueba usa una prueba modificada de Floyd-Warshall para mostrar que el orden de los cálculos en los 2 bucles internos no importa y que el gráfico permanece simétrico después de cada paso. Si mostramos que ambas condiciones son verdaderas, ambos algoritmos hacen lo mismo.

Definamos dist[i][j][k] como la distancia i-j usando usando sólo vértices del conjunto {0, ..., k} como vértices intermedios en el camino i-j.

dist[i][j][k-1] se define como el peso del borde desde i hasta j. Si no hay borde entre este peso se toma como infinito.

Ahora, utilizando la misma lógica que se utiliza en la prueba vinculado anteriormente:

dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1]) 

Ahora en el cálculo de dist[i][k][k] (y de manera similar para dist[k][i][k]):

dist[i][k][k] = min(dist[i][k][k-1], dist[i][k][k-1] + dist[k][k][k-1]) 

Ahora bien, como dist[k][k][k-1] no puede ser negativa (O tendríamos un negative loop en el gráfico), esto significa que dist[i][k][k] = dist[i][k][k-1]. Dado que si dist[k][k][k-1] = 0 ambos parámetros son los mismos, de lo contrario se elige el primer parámetro de min().

Así que ahora, debido a dist[i][k][k] = dist[i][k][k-1], al calcular dist[i][j][k] no importa si dist[i][k] o dist[k][j] permiten ya k en sus caminos. Como dist[i][j][k-1] solo se usa para el cálculo de dist[i][j][k], dist[i][j] se quedará dist[i][j][k-1] en la matriz hasta que se calcule dist[i][j][k]. Si i o j es igual a k, se aplica el caso anterior.

Por lo tanto, el orden de los cálculos no es importante.

Ahora tenemos que mostrar que dist[i][j] = dist[j][i] después de todos los pasos del algoritmo.

Comenzamos con una cuadrícula simétrica así dist[a][b] = dist[b][a], para todos a y b.

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 
      = min(dist[j][i], dist[k][i] + dist[j][k]) 
      = min(dist[j][i], dist[j][k] + dist[k][i]) 
      = dist[j][i] 

Por lo tanto nuestra tarea es a la vez verdadera y que mantendrá el invariante que dist[a][b] = dist[b][a]. Por lo tanto, dist[i][j] = dist[j][i] después de todos los pasos del algoritmo

Por lo tanto, ambos algoritmos arrojan el mismo resultado, correcto.

La velocidad es más fácil de probar. El ciclo interno se llama poco más de la mitad del número de veces que se lo llama normalmente, por lo que la función es aproximadamente el doble de rápida. Acabo de hacer un poco más lento porque todavía asigna el mismo número de veces, pero esto no importa, ya que min() es lo que ocupa la mayor parte de su tiempo.

Si ve algún error en mi prueba, por muy técnico que sea, indíquelo e intentaré solucionarlo.

EDIT:

Puede acelerar o ahorrar la mitad de la memoria cambiando el bucle como tal:

for (int k = 0; k < N; ++k) { 
    for (int i = 0; i < k; ++i) 
     for (int j = 0; j <= i; ++j) 
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[j][k]); 
    for (int i = k; i < N; ++i) { 
     for (int j = 0; j < k; ++j) 
      dist[i][j] = min(dist[i][j], dist[k][i] + dist[j][k]); 
     for (int j = k; j <= i; ++j) 
      dist[i][j] = min(dist[i][j], dist[k][i] + dist[k][j]); 
    } 
} 

Esto se divide lo anterior para los bucles del algoritmo optimizado, por lo sigue siendo correcto y es probable que obtenga la misma velocidad, pero usa la mitad de la memoria.

Gracias a Chris Elion por la idea.

Answer 2

(Usando la notación en el pseudo-código en el artículo de Wikipedia) Creo (pero no he probado) que si la matriz edgeCost es simétrica, entonces la matriz de ruta también será simétrica después de cada iteración. Por lo tanto, solo necesita actualizar la mitad de las entradas en cada iteración.

En un nivel inferior, solo necesita almacenar la mitad de la matriz (ya que d (i, j) = d (j, i)), por lo que puede reducir la cantidad de memoria utilizada y, con suerte, reducir el número de caché falla ya que accederá a los mismos datos varias veces.