Reconstruct the Shortest Path
When calculating the shortest path in a graph, it’s possible to also reconstruct it at the very end.
To do that, we can store the “parent” vertex for each vertex that we visit. Meaning that if we add the vertex
to in the queue after processing the vertex v, we can mark that the “parent” vertex of to was the vertex v. This will allow us to reconstruct the whole path at the end. We can start from the last node in the path and then move to its parent. Then move to the parent of the current node, and so on until reaching a node that doesn’t have a parent, which will be the starting node. This can be implemented by storing an additional parent array p:start = int(input()) # start vertex
d = [-1] * n # distance from start vertex
p = [-1] * n # parent 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
p[to] = v # parent of vertex is v
q.append(to) # add vertex to queue
# Reconstruction of the path from start to end
end = int(input()) # end vertex
path = [] # path from start to end
while end != -1: # while there is a parent vertex
path.append(end) # add vertex to path
end = p[end] # go to parent vertex
print(*path[::-1], sep=' -> ') # print the path in reverse orderSo, after adding each element to the queue, we mark its parent node in the array
p and then reconstruct the path at the very end by moving from the last node to the first one. In the end, the path should be printed in reverse order as we were adding elements from the end of the path and analyzing parent nodes one by one until reaching the start. So, to move from start to end, we need to reverse the path.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 and the end vertex is 0
p = [-1, -1, -1, -1],q = [3]
v = 3,q = []→ add all the neighbors that are not used to the queue
p = [-1, -1, 3, -1],q = [2]
v = 2,q = []→ add all the neighbors that are not used to the queue
p = [2, 2, 3, -1],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
- Reconstruct the path
end = 0→end = 2→end = 3
- print
3 → 2 → 0
Notice that if the
d[end] is still -1 by the end of the algorithm, then we were not able to actually reach the end vertex.Challenge: Find the Shortest Route
The Internet is a collection of computers that are connected to each other and can transfer data. In this case, those computers are enumerated from 1 to
n and we know the computers that are connected to each other. Alice wants to send a message to Bob and she would want to send that message as fast as possible. So, the route should be as short as possible.Alice has a computer with the number
a, and Bob’s computer number is b. You are asked to find an optimal route of computers that would transfer the message from Alice to Bob as fast as possible.Input
The first line of the input contains two integers
n (1 ≤ n ≤ 100 000) and e (1 ≤ e ≤ 100 000) the number of computers and the number of connections in the network.The next line contains two numbers
a and b (1 ≤ a, b ≤ n).The following
e lines contain pairs of integers c1, c2 (1 ≤ c1, c2 ≤ n) which means that the computer c1 is connected to the computer c2 and vice versa.Output
The program should print the most optimal route of the message where each computer number should be separated by a space. In the case of several optimal routes, it can print any of those.
Examples
Input | Output |
5 5
1 5
1 2
2 3
1 3
3 4
3 5 | 1 3 5 |
5 6
1 5
1 2
2 3
2 4
3 4
4 5
3 5 | 1 2 4 5 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB