Sin pesos, el camino más corto es el de menos aristas. La
búsqueda en amplitud lo calcula con una cola: la fuente sale primero, sus
vecinos entran con d = 1, los vecinos de estos con
d = 2, y cada vértice se descubre una sola vez, porque su
d deja de ser infinito. p[u] recuerda desde dónde
se llegó, y camino sube por p para reconstruir la
ruta. El panel muestra ssspBFS tal como está en el archivo
bfs.py del curso, la versión que no usa arreglo de visitados,
seguida de camino. Se ejecutan sobre cuatro grafos, uno con dos
componentes y otro con pesos donde la búsqueda se equivoca.
Entrada: un grafo no dirigido en listas de
adyacencia y una fuente s. Salida: las listas
d y p, y la ruta que devuelve camino
hasta un destino.
float("inf") y un guion para p = -1.
Blanco: sin descubrir. Azul: en la cola. Gris: ya salió de la cola.d[0] al terminar?
ssspBFS y la reconstrucciónssspBFS, la función camino arranca en
el destino; la ruta, ya volteada, se marca en verde sobre el
dibujo.Cargue el grafo de cuatro vértices con pesos y
ejecútelo completo: ssspBFS no recibe los pesos y entrega el camino
de menos aristas.
¿Por qué la búsqueda en amplitud no resuelve el problema cuando las aristas tienen peso?
Sin solución aquí. En el anillo con cuerda, cambie
el destino a cada uno de los siete vértices y anote d y
p; después diga cuántas veces se escribe d[u] en
cada vértice y por qué la respuesta es siempre la misma. En el grafo con
pesos, cambie el peso de la arista entre 0 y 3 de 9 a 5 y a 7 sobre el papel:
diga con cuál de los dos valores la búsqueda deja de equivocarse.