Diferencia entre DIjkstra y el algoritmo de BellmanFord

Question

Estoy escribiendo tesis sobre algoritmos de ruta más cortos. Y no entiendo una cosa ...

He hecho la visualización del algoritmo de dijkstras. 1) ¿Es correcto? ¿O estoy haciendo algo mal? 2) ¿Cómo se vería el algoritmo Bellman-Ford? Tan pronto como busqué la diferencia, encontré "Bellman-ford: la idea básica es muy similar a la de Dijkstra, pero en lugar de seleccionar los bordes vecinos más cortos, selecciona todos los bordes vecinos". Pero también dijkstra comprueba todos los vértices y todos los bordes, ¿no?

Answer 1

dijkstra asume que el costo de las rutas es monótonamente creciente. eso más la búsqueda ordenada (usando la cola de prioridad) sirve que cuando llegas por primera vez a un nodo, has llegado por la ruta más corta.

esto no es así con los pesos negativos. si usa dijkstra con pesos negativos, entonces puede encontrar que una ruta posterior es mejor que la anterior (porque un peso negativo mejoró la ruta en un paso posterior).

en bellman-ford, cuando llegue a un nodo, verifique si la nueva ruta es más corta. en contraste, con dijkstra, puede eliminar nodos

en algunos (la mayoría de los casos) dijkstra no explorará todas las rutas completas. por ejemplo, si G unía solo de regreso a C, entonces cualquier camino a través de G sería un costo mayor que cualquiera a través de C. bellman-ford consideraría todos los caminos a través de G a F (dijkstra nunca los miraría porque son de mayor costo que pasando por C). si no lo hace, no puede garantizar la búsqueda de bucles negativos.

he aquí un ejemplo: lo anterior nunca calcula la ruta AGEF. E ya ha sido marcado como visitado por el tiempo que llega desde G.

Answer 2

Pienso también en el mismo algoritmo de Dijkstra

resuelve el problema de una sola fuente de ruta más corta cuando todos los bordes tienen pesos no negativos. Es un algoritmo codicioso y similar al algoritmo de Prim. El algoritmo comienza en el vértice fuente, s, crece un árbol, T, que finalmente abarca todos los vértices alcanzables desde S. Los vértices se agregan a T por orden de distancia, es decir, primero S, luego el vértice más cercano a S, luego el siguiente más cercano , y así.