Tengo alrededor de 70k nodos, y 250k bordes, y el gráfico no está necesariamente conectado. Obviamente, usar un algoritmo eficiente es crucial. ¿Que recomiendas?Encontrar todos los caminos más cortos de cada par de nodos en un gráfico
Como nota al margen, agradecería consejos sobre cómo dividir la tarea entre varias máquinas. ¿Es posible incluso con este tipo de problema?
Gracias
Puede usar el Floyd-Warshall algorithm. Resuelve exactamente este problema.
La complejidad es O (V^3). También hay Johnson's algorithm con una complejidad de O (V^2 * log V + VE). Este último también es fácil de distribuir porque ejecuta el algoritmo de Dijkstra V veces, lo que se puede hacer en paralelo.
Hm. Pero tiene una complejidad 'O (n^3)'. Puede no ser muy eficiente. – dirkgently
@dirkgently: De hecho, la complejidad sería algo así como O (V^2 + V * E). Eso no es rápido, pero probablemente no puedas obtener mucho más si quieres salidas V^2. – jpalecek
@jpalecek: Me refería a la publicación original y a Floyd Warshall en particular. – dirkgently
MapReduce es un gran algoritmo distribuido para esto, aunque podría ser un poco demasiado alta potencia. Si está interesado en eso, eche un vistazo al this lecture o quizás este blog post para inspiración. (De hecho, cuando me enseñaron MapReduce, este fue uno de los primeros ejemplos.)
Para 250k bordes y 70k, parece que el gráfico es relativamente escasa, Dijkstra's algorithm carreras en O(E + V log V) para cada nodo, para un funcionamiento completo hora (todas las fuentes) de O(VE + V^2 log V). Esto debería ser lo suficientemente rápido, pero las advertencias habituales se aplican a Dijkstra. (Bordes negativos.)
También puede consultar Johnson's algorithm si su problema tiene que ver con pesos negativos, pero no con ciclos negativos. Específicamente, también se puede distribuir, ya que toma el gráfico ponderado y ejecuta el algoritmo de Dijkstra de cada nodo.
Los últimos enlaces no aparecen: http://en.wikipedia.org/wiki/Dijkstra's_algorithm y http://en.wikipedia.org/wiki/Johnson's_algorithm – Larry
Debe leer sobre la sintaxis de rebajas para cómo formatear tu publicación. +1 de todos modos de mí. –
Lea aquí: http://stackoverflow.com/editing-help –
Existen dos formas ingenuas de paralelizar este problema:
1) Identifique los subcomponentes y distribúyalos en diferentes equipos. La longitud del camino entre dos nodos de dos componentes diferentes no está definida.
2) Cargue el gráfico en diferentes computadoras y dé a cada computadora una lista de nodos para calcular todas las rutas más cortas. Los resultados para un nodo no dependen de los resultados de otro nodo, por lo que puede paralelizar este problema.
Al revés: no es demasiado difícil de implementar pero solo lo haría así si tuviera que resolver esto una vez. Si esto es un problema recurrente, es posible que desee ver los algoritmos distribuidos.
Use igraph, está escrito en C, bastante rápido y puede usar Python como lenguaje de envoltura.
Consulte los documentos/publicaciones que tienen las siguientes palabras clave: algoritmos de búsqueda de gráficos distribuidos. Here uno que puede ser de ayuda.
Hay esta cuenta ACM sólo papel así: Distributed computation on graphs: shortest path algorithms
Estás en lo correcto, esto no es un problema de tarea, sólo un proyecto para la diversión. No había considerado las aproximaciones, pero en este caso necesito obtener la ruta real entre dos nodos, y no solo la distancia. No veo cómo una aproximación realmente podría ayudar en este caso, pero estaría interesado en saber cómo hacerlo si pudieran. Editar: Esto fue en respuesta a un comentario que fue eliminado. Oh bien. – awegawef
Lo siento, lo borréSolo preguntaba si habías considerado resolver el uso de aproximaciones, pero luego decidí no preguntar de todos modos ya que ya aceptaste una respuesta. :) –
Y una aproximación en este contexto sería una ruta que no se garantiza que sea la más corta, pero se garantiza que no será más de un x% más larga que la ruta más corta. –