algorithm - operaciones - Dijkstra vs. Floyd-Warshall: Encontrar la ruta óptima en todos los pares de nodos
floyd warshall c++ (4)
Como han señalado otros, Floyd-Warshall se ejecuta a tiempo O (n 3 ) y ejecuta una búsqueda de Dijkstra desde cada nodo a cada otro nodo, suponiendo que está utilizando un montón de Fibonacci para respaldar la implementación de su Dijkstra, toma O (mn + n 2 log n). Sin embargo, no siempre se puede ejecutar de manera segura Dijkstra en un gráfico arbitrario porque el algoritmo de Dijkstra no funciona con los pesos negativos.
Hay un algoritmo verdaderamente notable llamado algoritmo de Johnson que es una ligera modificación para ejecutar el algoritmo de Dijkstra desde cada nodo que permite que ese enfoque funcione incluso si el gráfico contiene bordes negativos (siempre que no haya ciclos negativos). El algoritmo funciona ejecutando primero Bellman-Ford en el gráfico para transformarlo en un gráfico sin bordes negativos, luego usando el algoritmo de Dijkstra comenzando en cada vértice. Debido a que Bellman-Ford se ejecuta en tiempo O (mn), el tiempo de ejecución asintótico general sigue siendo O (mn + n 2 log n), por lo que si m = o (n 2 ) (tenga en cuenta que esto es poco-o de n), el enfoque es asintóticamente más rápido que usar Floyd-Warshall.
El único inconveniente aquí es que esto supone que tienes el algoritmo de Dijkstra respaldado por un montón de Fibonacci. Si no tiene el montón de Fibonacci disponible y no está dispuesto a poner en las 72 horas necesarias para construir, depurar y probar uno, entonces todavía puede utilizar un montón binario para el algoritmo de Dijkstra; simplemente aumenta el tiempo de ejecución a O (m log n), por lo que esta versión del algoritmo de Johnson se ejecuta en O (mn log n). Esto ya no es siempre más rápido que Floyd-Warshall, porque si m = Ω (n 2 ) entonces Floyd-Warshall se ejecuta en O (n 3 ) mientras que el algoritmo de Johnson se ejecuta en O (n 3 log n). Sin embargo, para gráficos dispersos, donde m = o (n 2 / log n), esta implementación del algoritmo de Johnson es aún mejor que la de Floyd-Warshall
En breve:
- Con un montón de Fibonacci, el algoritmo de Johnson es siempre tan bueno como el de Floyd-Warshall, aunque es más difícil codificar.
- Con un montón binario, el algoritmo de Johnson es por lo general tan bueno como Floyd-Warshall, pero no es una buena opción cuando se trata de gráficos grandes y densos.
¡Espero que esto ayude!
Estoy leyendo el algoritmo de Dijkstra y el algoritmo de Floyd-Warshall. Entiendo que Dijkstra''s encuentra la ruta óptima desde un nodo a todos los otros nodos y Floyd-Warshall encuentra la ruta óptima para todos los emparejamientos de nodos.
Mi pregunta es si el algoritmo de Dijkstra sería más eficiente que Floyd si lo ejecuto en cada nodo para encontrar la ruta óptima entre todos los emparejamientos.
El tiempo de ejecución de Dijkstra es O (E + VlogV) donde Floyd''s es O (V 3 ). Si Dijkstra falla, ¿cuál sería su tiempo de ejecución en este caso? ¡Gracias!
La complejidad para ejecutar Dijkstra en todos los nodos será O (EV + V 2 logV). Esta complejidad es menor que O (V 3 ) sif E <V 2 .
Prácticamente, Floyd-Warshall es más rápido que Dijkstra en el camino más corto (generalmente !!)
Depende. Ejecutar Dijkstra para todos los nodos te da O(VE + V^2log V) , mientras que Floyd''s es O(V^3) . Si E = O(V^2) , entonces los dos son teóricamente idénticos, con Floyd siendo más rápido en la práctica. Si E = O(V) , ejecuta Dijkstra para todos los nodos si es mejor tanto en teoría como en la práctica.
Básicamente, ejecute Dijkstra desde todos los nodos si espera tener tantos bordes como tenga nodos, y ejecute Floyd si espera tener gráficos casi completos.