Longitud de la ruta más corta con BFS
A medida que el algoritmo BFS parte de un nodo y se va expandiendo gradualmente hacia sus vecinos, es posible encontrar la ruta más corta desde el nodo inicial hasta todos los demás nodos en el grafo. Para ello, necesitamos modificar un poco el algoritmo original. Utilizaremos un array de distancias
d, al que inicialmente asignaremos el valor -1 en todas sus posiciones. Si el valor de un vértice es -1, significa que dicho vértice aún no ha sido visitado. Si el valor es positivo, representa la distancia del vértice actual con respecto al punto de partida:from collections import deque
n, e = map(int, input().split()) # n: vértices, e: aristas
g = [[] for _ in range(n)] # grafo - lista de adyacencia
for _ in range(e): # leer aristas
a, b = map(int, input().split()) # a -> b y b -> a
g[a].append(b)
g[b].append(a)
start = int(input()) # vértice de inicio
d = [-1] * n # distancia desde el vértice de inicio
q = deque([start]) # cola de vértices
d[start] = 0 # la distancia desde start hasta sí mismo es 0
while q: # mientras la cola no esté vacía
v = q.popleft() # obtener el vértice de la cola
print(v, end=' ') # imprimir vértice
for to in g[v]: # para cada vértice conectado a v
if d[to] == -1: # si el vértice no se ha visitado
d[to] = d[v] + 1 # (start -> to) = (start -> v) + 1
q.append(to) # añadir el vértice a la cola
print(d)Aquí, primero inicializamos el array de distancias
d con -1. Esto sirve como indicación de que ningún vértice ha sido utilizado todavía. Luego, establecemos d[start] en 0, lo que significa que la distancia desde el vértice start hasta sí mismo es 0.Conforme el algoritmo procesa más nodos, sus valores correspondientes se actualizan en el array de distancias
d, proporcionando así las distancias de todos los nodos a partir del vértice start.Veamos cómo se comporta el algoritmo con varios ejemplos:
n = 4, e = 4
La entrada de pares
a, b es la siguiente: [(0, 1), (0, 2), (1, 2), (3, 2)]El vértice inicial es 3
d = [-1, -1, -1, 0],q = [3]
v = 3,q = []→ se añaden a la cola todos los vecinos que no han sido utilizados
d = [-1, -1, 1, 0],q = [2]
v = 2,q = []→ se añaden a la cola todos los vecinos que no han sido utilizados
d = [2, 2, 1, 0],q = [0, 1]
v = 0,q = [1]→ se añaden a la cola todos los vecinos que no han sido utilizados
v = 1,q = []→ se añaden a la cola todos los vecinos que no han sido utilizados
- Terminado
n = 5, e = 4
La entrada de pares
a, b es la siguiente: [(0, 1), (0, 2), (1, 2), (3, 4)]El vértice inicial es 0
d = [0, -1, -1, -1, -1],q = [0]
v = 0,q = []→ se añaden a la cola todos los vecinos que no han sido utilizados
d = [0, 1, 1, -1, -1],q = [1, 2]
v = 1,q = [2]→ se añaden a la cola todos los vecinos que no han sido utilizados
v = 2,q = []→ se añaden a la cola todos los vecinos que no han sido utilizados
- Terminado
Notice how nodes 3 and 4 were never visited.
They were not connected to the initial node 0.
Desafío: Encontrar la longitud de la ruta más corta
Dado un grafo no dirigido con
v vértices y e aristas, se pide calcular la distancia más corta entre el vértice 1 y el vértice v. Si no están conectados, el programa debe imprimir Impossible.Entrada
La primera línea de la entrada contiene dos enteros
v (1 ≤ v ≤ 100 000) y e (1 ≤ e ≤ 100 000).Las siguientes
e líneas contienen pares de enteros v1, v2 (1 ≤ v1, v2 ≤ v) que indican que el vértice v1 está conectado con el vértice v2 y viceversa.Salida
El programa debe imprimir la longitud de la ruta más corta entre
1 y v.Ejemplos
Entrada | Salida |
5 6
1 2
2 3
1 3
3 4
4 3
3 5 | 2 |
2 1
1 2 | 1 |
2 0 | Impossible |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB