Consider a problem to find the shortest path from a given starting node s to any other nodes in the (undirected) graph. The length of a path in the graph is the number of edges included. Complete the function shortest_path(adj_list, s), which takes the adjacency list of the graph and a starting node as input, and returns a list containing the length of the shortest path from the starting node to all other nodes. Note: If there is no path from the starting node to a node, set the length of shortest path as float('inf'). You can use any Python built-in package to implement the stack/queue/priority queue if needed. Hint: Consider the three graph traversal strategies (DFS, BFS and PFS) discussed in the class. Which one is applicable in this problem? For example: Test Result adj_list = [[], [2, 3], [1, 4], [1], [2]] d = shortest_path(adj_list, 0) print(d) d = shortest_path(adj_list, 2) print(d) [0, inf, inf, inf, inf] [inf, 1, 0, 2, 1]

To find the shortest path from a given starting node s to any other nodes in the (undirected) graph, we can use Breadth-First Search (BFS) algorithm. The basic idea of BFS is to explore all the vertices at distance 1 from the current vertex before moving on to vertices at distance 2.

Here is the implementation of the shortest_path function using BFS algorithm:

from collections import deque

def shortest_path(adj_list, s):
    n = len(adj_list)
    visited = [False] * n
    distance = [float('inf')] * n
    distance[s] = 0
    queue = deque([s])
    
    while queue:
        u = queue.popleft()
        visited[u] = True
        
        for v in adj_list[u]:
            if not visited[v]:
                visited[v] = True
                distance[v] = distance[u] + 1
                queue.append(v)
    
    for i in range(n):
        if not visited[i]:
            distance[i] = float('inf')
    
    return distance

In the above code, we first initialize two lists: visited and distance. The visited list is used to keep track of the visited nodes and the distance list is used to store the shortest distance from the starting node to all other nodes. We initialize all the distances as infinity except the distance of the starting node which is set to 0.

We then use a deque (double-ended queue) to implement the BFS algorithm. We start by adding the starting node to the queue. Then, while the queue is not empty, we remove a vertex u from the front of the queue and mark it as visited. We then iterate over all the neighbors v of u and if v is not visited, we mark it as visited, update its distance from the starting node and add it to the end of the queue.

Finally, we check if there are any nodes that were not visited during the BFS traversal and set their distance as infinity. We then return the distance list.

Let's use the above code to solve the given example:

adj_list = [[], [2, 3], [1, 4], [1], [2]]
d = shortest_path(adj_list, 0)
print(d) # Output: [0, inf, inf, inf, inf]

d = shortest_path(adj_list, 2)
print(d) # Output: [inf, 1, 0, 2, 1]

In the first test case, the starting node is 0 and there are no edges connected to it. Hence, the distance to all other nodes is infinity.

In the second test case, the starting node is 2 and the shortest path to node 2 is 0 (itself). The shortest path to node 1 is 1 (through node 2), the shortest path to node 3 is 2 (through nodes 2 and 1), and the shortest path to node 4 is 1 (through node 2).