La razón se reduce a los pesos de borde.
BFS SIEMPRE PUEDE resolver el problema de la ruta más corta de una sola fuente SI el peso de cada borde entre dos vértices en el gráfico es el mismo. Esto se debe a que BFS encontrará todas las rutas que están a 1 borde de la fuente, seguidas de todas las rutas que están a dos bordes de la fuente, y así sucesivamente. Si los bordes son todos de longitud x = 1 (o la misma longitud), entonces BFS encontrará todas las rutas de longitud 1x desde la fuente, seguidas por todas las rutas de longitud 2x, seguidas por todas las rutas de longitud 3x, y así sucesivamente. Esto permitirá que BFS encuentre la ruta más corta desde el nodo fuente a cualquier nodo receptor predeterminado.
¿Qué sucede si los pesos de los bordes no son los mismos? Entonces BFS no funciona. Esto se debe a que BFS termina cuando encuentra por primera vez el nodo sumidero en su búsqueda del gráfico.
- ¿Qué algoritmo se pregunta en la entrevista de Google?
- ¿Cuál es el mejor algoritmo para encontrar la ruta más corta en un gráfico orientado, donde algunos bordes están bloqueados y las teclas están en algún lugar de los nodos?
- ¿Cómo funciona el algoritmo de 'conteo' de Gmail?
- ¿Cómo se diseñaría una estructura de datos para soportar las siguientes operaciones en tiempo logarítmico: insert, deleteMin, deleteMax findMin, findMax?
- ¿Por qué se utilizan montones para la asignación de memoria? ¿Por qué no se utilizan pilas ni ninguna otra?
Tomemos, por ejemplo, el gráfico que construí a continuación.
Hay dos caminos desde la fuente hasta el sumidero. La ruta A es de longitud 3 y la ruta B es de longitud 501. Sin embargo, la ruta B solo tiene dos aristas mientras que la ruta A tiene 3 aristas. Para comprender por qué BFS no funcionará, debe observar la mecánica de cómo se ejecutaría en este caso. BFS termina cuando descubre por primera vez el nodo sumidero. Lo que esto significa es que encuentra el camino más corto desde la fuente hasta el sumidero. Como mencioné anteriormente, BFS examina todas las rutas que están a un borde de distancia, seguido de todas las rutas que están a dos bordes de distancia, y así sucesivamente, hasta que encuentra el nodo sumidero (ignorando los ciclos marcando qué nodos ya han sido visitados). En este caso, lo que eso significa es que BFS primero descubrirá el nodo de sumidero G a lo largo de la ruta B, ya que B solo tiene dos bordes y todas las rutas de longitud a dos bordes del nodo de origen se buscan antes de todas las rutas de longitud 3 bordes. El algoritmo BFS devolvería erróneamente que la ruta B es más corta que la ruta A, a pesar de que la longitud ponderada de la ruta B es 501, mientras que la longitud ponderada de la ruta A es solo 3. Esto se debe a que BFS nunca se ocupa de la ponderación de la bordes, en cambio, solo se tiene en cuenta la cantidad de bordes en una ruta en particular.
Es por eso que si tiene un gráfico con bordes ponderados, debe usar el Algoritmo de Dijkstra [1] en lugar de BFS. La disparidad fundamental aquí es que BFS supone (si todos los bordes están ponderados 1) que el número de bordes en una ruta es igual a la longitud de esa ruta. Sin embargo, este no es siempre el caso.
Aparte: ahora, lo que podría hacer si está configurado en BFS es transformar su gráfico de manera que cualquier borde de longitud y> 1 se pueda convertir en una ruta de longitud y bordes e y -1 nodos, con cada borde teniendo un peso de 1. Entonces puede usar BFS en la versión transformada de su gráfico ponderado ya que los pesos de borde serían todos 1. A menudo, los costos de tiempo de ejecución son demasiado altos para hacerlo en la práctica. De manera análoga, siempre que transforme todos los pesos de borde para que sean iguales (no necesariamente de longitud 1, podría ser longitud 2, 3, 4, etc.), BFS seguirá funcionando.
Notas al pie
[1] Algoritmo de Dijkstra
