← Volver a los ejercicios

Amplitud

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.

1. El grafo y la predicción

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.

Grafo:

Sobre cada vértice, d/p, con ∞ para float("inf") y un guion para p = -1. Blanco: sin descubrir. Azul: en la cola. Gris: ya salió de la cola.
Fuente 0. Destino: ¿Cuánto vale d[0] al terminar?

2. Ejecute ssspBFS y la reconstrucción

q: sin crear
d: sin crear
p: sin crear
ruta: sin crear
Paso 0 de 0
La arista azul es la que se está mirando y se pone verde cuando el otro extremo estaba sin descubrir y entra a la cola. Al terminar ssspBFS, la función camino arranca en el destino; la ruta, ya volteada, se marca en verde sobre el dibujo.

3. Con pesos

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?

4. Para llevarse

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.