BFS Shortest Path Length
As the BFS algorithm starts from one node and gradually expands to the neighbors, it’s possible to find the shortest path from the starting node to all the other nodes in the graph. We need to modify the initial algorithm a bit to do that. We will have a distance array
d, which will have all the values set to -1 initially. If the value of a vertex is -1, then the vertex isn’t visited yet. If the value is positive, the value represents the distance of the current vertex from the starting point:from collections import deque
n, e = map(int, input().split()) # n: vertices, e: edges
g = [[] for _ in range(n)] # graph - adjacency list
for _ in range(e): # read edges
a, b = map(int, input().split()) # a -> b and b -> a
g[a].append(b)
g[b].append(a)
start = int(input()) # start vertex
d = [-1] * n # distance from start vertex
q = deque([start]) # queue of vertices
d[start] = 0 # distance from start to start is 0
while q: # while the queue is not empty
v = q.popleft() # get vertex from queue
print(v, end=' ') # print vertex
for to in g[v]: # for each vertex connected to v
if d[to] == -1: # if vertex is not visited
d[to] = d[v] + 1 # (start -> to) = (start -> v) + 1
q.append(to) # add vertex to queue
print(d)Here we first initialize the distance array
d with -1s. This acts as an indication that none of the vertices were used yet. Then we set the value of d[start] to 0, which means that the distance from the vertex start to start is 0.As the algorithm processes more nodes, their corresponding values are updated in the distance array
d, giving us all the distance values for all the nodes starting from the vertex start.Let’s simulate the algorithm on several inputs:
n = 4, e = 4
The input
a, b pairs are the following: [(0, 1), (0, 2), (1, 2), (3, 2)]The starting vertex is 3
d = [-1, -1, -1, 0],q = [3]
v = 3,q = []→ add all the neighbors that are not used to the queue
d = [-1, -1, 1, 0],q = [2]
v = 2,q = []→ add all the neighbors that are not used to the queue
d = [2, 2, 1, 0],q = [0, 1]
v = 0,q = [1]→ add all the neighbors that are not used to the queue
v = 1,q = []→ add all the neighbors that are not used to the queue
- Done
n = 5, e = 4
The input
a, b pairs are the following: [(0, 1), (0, 2), (1, 2), (3, 4)]The starting vertex is 0
d = [0, -1, -1, -1, -1],q = [0]
v = 0,q = []→ add all the neighbors that are not used to the queue
d = [0, 1, 1, -1, -1],q = [1, 2]
v = 1,q = [2]→ add all the neighbors that are not used to the queue
v = 2,q = []→ add all the neighbors that are not used to the queue
- Done
Notice how nodes 3 and 4 were never visited.
They were not connected to the initial node 0.
Challenge: Find the Shortest Path Length
Given an undirected graph with
v vertices and e edges, you are asked to calculate the shortest path between vertex 1 and vertex v. If they are not connected, the program should print Impossible.Input
The first line of the input contains two integers
v (1 ≤ v ≤ 100 000) and e (1 ≤ e ≤ 100 000).The following
e lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.Output
The program should print the length of the shortest path between
1 and v Examples
Input | Output |
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