Comparación de los algoritmos de Dijkstra y Floyd-Warshall

Propósitos principales:

• El algoritmo de Dijkstra es un ejemplo de un algoritmo SSSP o más corto de fuente única, es decir, dado un vértice fuente, encuentra la ruta más corta desde la fuente hasta todos los demás vértices.
• El algoritmo Floyd Warshall es un ejemplo de algoritmo de ruta más corta de todos los pares, lo que significa que calcula la ruta más corta entre todos los pares de Nodes.

Complejidades de tiempo:

• Complejidad temporal del algoritmo de Dijkstra: O(E log V)
• Complejidad temporal de Floyd Warshall: O(V ³ )

Otros puntos:

• Podemos usar el algoritmo de camino más corto de Dijskstra para encontrar todos los pares de caminos más cortos ejecutándolo para cada vértice. Pero la complejidad del tiempo de esto sería O (VE Log V) que puede ir (V ³ Log V) en el peor de los casos.
• Otro factor diferenciador importante entre los algoritmos es su trabajo hacia sistemas distribuidos. A diferencia del algoritmo de Dijkstra, Floyd Warshall se puede implementar en un sistema distribuido, lo que lo hace adecuado para estructuras de datos como Graph of Graphs (usado en mapas).
• Por último, Floyd Warshall funciona para bordes negativos pero no para ciclos negativos , mientras que el algoritmo de Dijkstra no funciona para bordes negativos.

Este artículo es una contribución de Vineet Joshi . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.