algorithm - redes - ruta mas corta youtube
El mejor algoritmo de ruta más corto. (7)
Dijkstra encuentra el camino más corto desde un solo vértice, Floyd-Warshall lo encuentra entre todos ellos.
¿Cuál es la diferencia entre el "algoritmo Floyd-Warshall" y el "algoritmo de Dijkstra" , y cuál es la mejor para encontrar la ruta más corta en una gráfica?
Necesito calcular la ruta más corta entre todos los pares en una red y guardar los resultados en una matriz de la siguiente manera:
**A B C D E**
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0
Dijkstra es principalmente para la búsqueda de ruta más corta de un solo par, es decir, de un nodo a todos los demás nodos, mientras que Floyd-Warshall es para la ruta más corta de todos los pares, es decir, la ruta más corta entre todos los pares de vértices. El algoritmo Floyd-Warshall tiene un peor desempeño de O (| V | 3), mientras que el de Dijkstra tiene un peor desempeño de O (| E | + | V | log | V |) Además, el Dijkstra no se puede usar para pesos negativos (Utilizamos Bellmann Ford para el mismo). pero para Floyd-Warshall podemos usar pesos negativos pero no ciclos negativos
El algoritmo de Dijkstra encuentra la ruta más corta entre un nodo y todos los demás nodos del gráfico. Lo ejecutarías una vez por cada nodo. Los pesos deben ser no negativos, por lo que si es necesario, primero debe normalizar los valores en el gráfico.
Floyd-Warshall calcula las rutas más cortas entre todos los pares de nodos en una sola ejecución! Los pesos de los ciclos no deben ser negativos, y el gráfico debe ser dirigido (su diagrama no lo es).
El algoritmo de Johnson está usando el algoritmo de Dijkstra para encontrar todos los pares en una sola pasada, y es más rápido para árboles dispersos (vea el enlace para análisis).
Floyd Warshall encuentra los caminos entre todos los pares de vértices, pero Dijkstra solo encuentra el camino de un vértice a todos los demás.
Floyd Warshall es O (| V | 3 ) y Dikstra es O (| E | + | V | log | V |) pero tendrá que ejecutarlo V veces para encontrar todos los pares, lo que da una complejidad de O (| E * V | + | V 2 | log | V |) Supongo. Esto significa que posiblemente sea más rápido usar Dijsktra repetidamente que el algoritmo FW, probaría ambos enfoques y vería cuál es el más rápido en el caso real.
Mientras tanto, se conocen mejores algoritmos para el problema de la ruta más corta de una sola fuente. Uno prácticamente relevante es una derivación del algoritmo de Dijkstra por Torben Hagerup . El algoritmo tiene la misma complejidad de caso peor que la de Djikstra, pero en el caso promedio, el tiempo de ejecución esperado es lineal en el tamaño del gráfico, que es mucho más rápido que el Dijkstra puro. La idea del algoritmo se basa en la idea de que no es necesario sondear siempre el límite mínimo de la cola. Es posible encuestar un borde de la cola, cuyo peso es 1+k veces más grande que el peso mínimo del borde, donde k es un número mayor de 0 . Incluso si se elige tal borde, el algoritmo seguirá encontrando la ruta más corta.
Utilice el algoritmo Floyd-Warshall si desea encontrar la ruta más corta entre todos los pares de vértices, ya que tiene un tiempo de ejecución (mucho más alto) que el algoritmo de Dijkstra.
El algoritmo Floyd-Warshall tiene un peor desempeño de O (| V | 3 ), mientras que el de Dijkstra tiene un peor desempeño de O (| E | + | V | log | V |)
Principales propósitos:
El algoritmo de Dijkstra es un ejemplo de un algoritmo SSSP más corto o de una sola fuente, es decir, dado un vértice fuente, encuentra la ruta más corta desde la fuente a todos los demás vértices. Floyd Warshall Algorithm 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 nodos.
Complejidades de tiempo:
Complejidad temporal del algoritmo de Dijkstra: O (E log V)
Complejidad temporal de Floyd Warshall: O (V3)
Otros puntos:
Podemos usar el algoritmo de ruta más corta de Dijskstra para encontrar todas las rutas más cortas de par ejecutándolo para cada vértice. Pero la complejidad del tiempo de esto sería O (VE Log V), que puede ir (V3 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 (utilizado en mapas).
Por último, Floyd Warshall funciona con borde negativo pero sin ciclo negativo, mientras que el algoritmo de Dijkstra no funciona con bordes negativos