Según esta página , el algoritmo de Dijkstra es solo BFS con una cola de prioridad. ¿Es realmente así de simple? Yo creo que no.
algorithms
graphs
shortest-path
Barry Fruitman
fuente
fuente
Respuestas:
Puede implementar el algoritmo de Dijkstra como BFS con una cola prioritaria (aunque no es la única implementación).
El algoritmo de Dijkstra se basa en la propiedad de que la ruta más corta de a t es también la ruta más corta a cualquiera de los vértices a lo largo de la ruta. Esto es exactamente lo que hace BFS.s t
O en otra perspectiva: ¿cómo se comportaría el algoritmo de Dijkstra si todos los pesos fueran 1? Exactamente como BFS.
fuente
Aquí hay una idea del libro "Algoritmos (Sección 4.4)" de Dasgupta et al:
Para cualquier borde de E (con peso l e ), reemplácelo por l e bordes de longitud 1 , agregando l e - 1 nodos ficticios entre u y v .e = ( u , v ) mi lmi lmi 1 lmi- 1 tu v
Como resultado, todos los bordes del gráfico de resultados tienen longitud unitaria. Por lo tanto, podemos calcular distancias en G ejecutando BFS en G ' .G′ G G′
BFS en puede ser muy lento si algunos l e son grandes porque se malgasta demasiado tiempo en las distancias a los nodos de computación ficticias que no importa en absoluto. El algoritmo de Dijkstra lo evita al establecer distancias estimadas para los nodos y relajarlos siempre que sea posible.G′ le
Se comporta exactamente igual que BFS. Elaboramos esto desde dos puntos principales.
Sobre "relajación".
Para el algoritmo de Dijkstra en gráfico general ponderado, la relajación es
En "cola de prioridad".
Cuando el algoritmo de Dijkstra se ejecuta en un gráfico no ponderado, en cualquier momento, la cola de prioridad contiene como máximo dos valores distintos (distancia). Por lo tanto, una cola FIFO de BFS es suficiente.
fuente