must use python

Community Answer

【General guidance】The answer provided below has been developed in a clear step by step manner.Step1/21. This problem can be solved using Dijkstra’s algorithm.2. We will use a modified version of BFS(Breadth-first search).3. BFS is used to store the predecessor of a given vertex.4. Time Complexity : O(V + E)5. Auxiliary Space: O(V)ExplanationWe can use above points to better understand the problem.Explanation:Please refer to solution in this step.Step2/2Solution of above problem in python language ins given below:# our objective to find the shortest path in an unweighted graph.# function to form edge between two vertices source and destdef add_edge(adj, src, dest):adj[src].append(dest);adj[dest].append(src);# Implementation of BFSdef BFS(adj, src, dest, v, pred, dist):# a queue to maintain queue of vertices whose# adjacency list is to be scanned as per normal# DFS algorithmqueue = []# boolean array visited[] which stores the# information whether ith vertex is reached# at least once in the Breadth first searchvisited = [False for i in range(v)];# initially all vertices are unvisited# so v[i] for all i is false# and as no path is yet constructed# dist[i] for all i set to infinityfor i in range(v):dist[i] = 1000000pred[i] = -1;# now source is first to be visited and# distance from source to itself should be 0visited[src] = True;dist[src] = 0;queue.append(src);# standard BFS algorithmwhile (len(queue) != 0):u = queue[0];queue.pop(0);for i in range(len(adj[u]) ... See the full answer