Puede intentar hacer una versión de Floyd-Warshall que sea más rápida en matrices dispersas.
Primero, recordemos lo que hace este algoritmo:
MMi,ji→jMi,j=∞
Vki,j
Mi,j←min{Mi,j,Mi,k+Mk,j}.
Claramente, si o entonces no es necesario realizar ninguna actualización. Por lo tanto, en los primeros pasos del algoritmo, solo necesitamos realizar aproximadamente comparaciones donde y denotan el número de bordes entrantes y salientes del -ésimo nodo respectivamente. A medida que avanza el algoritmo, se llenan más y más entradas de la matrizPor lo tanto, los últimos pasos pueden llevar mucho más tiempo.Mi,k=∞Mk,j=∞degin(k)⋅degout(k)degin(k)degout(k)kM
Tenga en cuenta que necesitamos una manera eficiente para repetir sólo las células sobre los no-infinitos en el fila ésima y la columna de la matriz. Esto se puede hacer manteniendo un conjunto de bordes entrantes y salientes para cada nodo.k
Parece que los primeros pasos del algoritmo pueden beneficiarse enormemente de la escasez. Por ejemplo, un gráfico construido aleatoriamente con sugiere que la primera iteración ( ) es solo pasos. Si el gráfico se divide en muchos componentes conectados, la matriz permanecería relativamente escasa en todo el algoritmo y el tiempo de ejecución total podría ser tan bajo como . Por otro lado, si el gráfico contiene solo un componente conectado, entonces la última iteraciónse espera que tome pasos. En este caso, el tiempo de ejecución total podría ser . Tan grande como la versión no dispersa.E=O(V)k=0O(1)MO(V)k=|V|O(V2)O(V3)