Todos los pares del camino más corto en grafos no dirigidos y no ponderados

Question

Soy consciente de que el camino más corto de origen único en un grafo no dirigido y no ponderado puede resolverse fácilmente mediante BFS.

Para el caso del problema del camino más corto de todos los pares, ¿hay alguna solución mejor que ejecutar una BFS para cada nodo?

Answer 1

No tengo ni idea de por qué esta pregunta se consideró fuera de tema para CSTheory. Ciertamente, esta pregunta es muy interesante para los que trabajan en algoritmos de grafos.

Para ese grupo, preguntarse si existe una solución mejor para APSP que ejecutar BFS desde cada nodo, equivale a preguntarse si existe un algoritmo que se ejecute en un tiempo asintóticamente menor que $O(mn+n^2)$ tiempo donde $m$ es el número de aristas y $n$ es el número de nodos. Es un gran problema pendiente mejorar significativamente este tiempo de ejecución.

Timothy Chan descubrió algunas pequeñas mejoras algorítmicas en SODA'06 que pueden ser prometedoras en la práctica (él las puso en práctica). Véase el artículo:

Timothy M. Chan: All-pairs shortest paths for unweighted undirected graphs in o(mn) time. SODA 2006: 514-523

En el caso no dirigido y no ponderado, se puede resolver el problema mediante reducciones a la multiplicación de matrices de $n \times n$ (en teoría, esto significa que se puede obtener $n^{2.376}$ tiempo). Si el grafo es denso, puede resultar muy útil. Estos algoritmos son bastante ingeniosos:

Zvi Galil, Oded Margalit: All Pairs Shortest Distances for Graphs with Small Integer Length Edges. Inf. Comput. 134(2): 103-139 (1997)

Zvi Galil, Oded Margalit: All Pairs Shortest Paths for Graphs with Small Integer Length Edges. J. Comput. Syst. Sci. 54(2): 243-254 (1997)

Raimund Seidel: On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs. J. Comput. Syst. Sci. 51(3): 400-403 (1995)

Es de esperar que las exposiciones de los tres últimos (o los propios artículos) puedan encontrarse libremente en la Web.

Answer 2

Tuve que escribir una implementación rápida de esto para tratar con grafos grandes, y descubrí que el n BFS era mucho mejor que el algoritmo Floyd-Warshall. Su forma de almacenar los resultados, sin embargo (una matriz de predecesores) sigue siendo una muy buena manera de almacenar el resultado ! mucho mejor que almacenar $\binom n 2$ (incluso cuando son cortas), especialmente para un uso compacto de la memoria.

Nathann

Answer 3

Puede que sea posible encontrar todos los caminos más cortos (sólo distancias) en $O(n^2 log\ n)$ tiempo y $O(n^2)$ espacio si el siguiente papel es cierto:

Udaya Kumar Reddy K. R, y K. Viswanathan Iyer: All-pairs shortest-paths problem for unweighted graphs in $O(n^2 log\ n)$ tiempo
Academia Mundial de Ciencia, Ingeniería y Tecnología Vol:3 (2009)

Tenga en cuenta que La Academia Mundial de Ciencias se considera depredadora así que yo diría que hay que comprobar cuidadosamente ese papel si es realmente cierto.