Si observa las diferencias entre Breadth-first search y Dijkstra SSSP. Lo primero que notará es que BFS usa la cola Normal mientras que Dijkstra SSP usa la cola de prioridad. Por qué esto es tan ?
Considere este gráfico ponderado.
una
10 / \ 5
/ \
antes de Cristo
8 / \ 8
\ /
re
- ¿Qué es el cuello de botella de von Neumann y cómo se puede evitar?
- ¿Cuáles son ejemplos de problemas que se creía que eran NP completos pero que en realidad son P?
- ¿Qué hace que ML en Biología Computacional sea especialmente difícil?
- ¿Puedo encontrar la contraseña de un archivo comprimido si se conoce el contenido de los archivos incluidos?
- ¿A dónde va el contenido medio descargado si detenemos la descarga a mitad de camino?
Ahora si ejecutamos BFS en este gráfico para calcular la ruta más corta entre los nodos a y d.
Sería algo como lo siguiente.
Operación Nodo actual Cola Rutas actuales
Iniciar NULL [] []
Poner en cola a [a] [a]
Dequeue a [] [a]
Poner en cola a [b, c] [a]
Ahora aquí, dependiendo del orden de inserción, BFS producirá
Resultado diferente.
Caso 1. Cuando la cola es [b, c]
DEQEUE b [c] [a, b]
ENQUEUE b [c, d] [a, b]
DEQUEUE c [d] [[a, b], [a, c]]
ENQUEUE c [d, d] [[a, b], [a, c]]
DEQUEUE d [d] [[a, b, d], [a, c]]
Desde que alcanzamos el nodo objetivo, BFS terminará aquí dando [a, b, d]
como con el costo 18.
Caso 2. Cuando la cola es [c, b]
A diferencia del caso anterior, si se exploraba c primero, BFS habría dado
[a, c, d] como ruta con costo 13.
Por lo tanto, el resultado se ve afectado por el orden de inserción en la cola. Nosotros
puede solucionar este problema recogiendo bordes de menor peso en la cola
operación (que se puede lograr mediante el uso de la cola de prioridad mínima). Leer
sobre Dijkstra SSSP para más detalles.
