How can I increase speed performance of this Python 3 programming challenge?
Find the shortest path from one point to another (last line)
4 4 1 2 4 1 2 3 3 1 2 4
4--3 | /| |/ | 1--2
The shortest path: 2-1-4
import sys from queue import Queue def bfs(graph, start, end): global distance # path var for store current path path = () Q = Queue() Q.put(start) # visited dict, store key - visited vertices, value - path from the start # query - to store current queue items while Q.empty() is False: # take last element from the queue u = Q.get() path = path + (u,) # set it to visited and add current path if u == end: return distance[end] # go trough its children for child in graph[u]: if distance[child] == 0: # add it to queue Q.put(child) distance[child] = distance[u] + 1 else: return -1 if __name__ == '__main__': global distance input = sys.stdin.read() data = list(map(int, input.split())) n, m = data[0:2] data = data[2:] adj = [ for _ in range(n)] distance = [0 for _ in range(n)] edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2])) edges.sort() for (a, b) in edges: adj[a - 1].append(b - 1) adj[b - 1].append(a - 1) s, t = data[2 * m] - 1, data[2 * m + 1] - 1 print(bfs(adj, s, t))
This code must build a graph adjacency list in format [[0,2], where list index is graph node index, and numbers are connected edges to it.
The input format is next:
3 2 1 2 2 3
where the first two numbers is the number of vertexes (3) and number of edges (2), and the next lines describe the connections through graph vertices.