algorithm - recorrido - ¿Cuál es la diferencia entre BFS y los algoritmos de Dijkstra al buscar el camino más corto?
dijkstra algorithm (2)
Blockquote mientras usamos BFS para encontrar el camino más corto en un gráfico, lo que hacemos es Descubrimos todos los vértices conectados, los agregamos a la cola y también mantenemos la distancia desde la fuente hasta ese vértice. Ahora, si encontramos una ruta desde el origen hasta ese vértice con aún menos distancia, ¡entonces lo actualizamos!
No mantenemos una distancia en BFS. Es para el descubrimiento de nodos. Entonces los colocamos en una cola general y los mostramos. a diferencia de Dijikstra donde ponemos el peso acumulativo del nodo (después de la relajación) en una cola de prioridad y hacemos estallar la distancia mínima.
Entonces BFS funcionaría como dijikstra en un gráfico de igual peso porque.
la complejidad varía debido al uso de cola simple y cola de prioridad.
Estaba leyendo acerca de los algoritmos de Graph y encontré estos dos algoritmos.
¡Busqué mucho sobre esto pero no obtuve ninguna respuesta satisfactoria!
Tengo una duda de cuál es la diferencia entre el algoritmo de Dijkstra y BFS mientras busco el camino más corto.
al usar BFS para encontrar el camino más corto en un gráfico, lo que hacemos es
Descubrimos todos los vértices conectados, los agregamos a la cola y también mantenemos la distancia desde la fuente hasta ese vértice. Ahora, si encontramos una ruta desde el origen hasta ese vértice con aún menos distancia, ¡entonces lo actualizamos!
¡Esto es exactamente lo mismo que hacemos en el algoritmo de Dijkstra! entonces, ¿cuál es la diferencia entre Dijkstra''s y BFS? Y entonces, ¿por qué las complejidades de tiempo de estos algoritmos son tan diferentes?
Si alguien puede explicarlo con la ayuda de un pseudo código, ¡le estaré muy agradecido!
¡Sé que me estoy perdiendo algo! ¡Por favor ayuda!
La búsqueda de primer orden es solo el algoritmo de Dijkstra con todos los pesos de borde igual a 1.
El algoritmo de Dijkstra es conceptualmente la búsqueda de ancho que respeta los costos de los bordes.
El proceso para explorar el gráfico es estructuralmente el mismo en ambos casos.