If we want to compute the minimum number of flight segments between a starting city and target city, we can construct an undirected graph. In the graph the nodes represent cities and the edges represent the flight segments. We can count the number of segments to determine the shortest distance.<\/p>\n\n\n\n
The following can be applied to any situation in finding the shortest path. It is an implementation of the breadth first search algorithm.<\/p>\n\n\n\n
See code below.<\/p>\n\n\n\n\n\n\n\n
Problem: <\/strong>Given an undirected graph with n vertices and m edges and two vertices u and v, compute the length of a shortest path between u and v (that is, the minimum number of edges in a path from u to v).<\/p>\n\n\n\n Input Format: <\/strong>An undirected graph with n vertices and m edges. The next line contains two vertices u and v of the graph.<\/p>\n\n\n\n Constraints:<\/strong> 2 \u2264 n \u2264 10^5 , 0 \u2264 m \u2264 10^5 , u 6 = v, 1 \u2264 u, v \u2264 n.<\/p>\n\n\n\n Result: <\/strong>Integer value of the minimum number of edges in a path from u to v, or \u22121 if there is no path.<\/p>\n\n\n\n Computing the Minimum Number of Flight Segments If we want to compute the minimum number of flight segments between a starting city and target city, we can construct an undirected graph. In the graph the nodes represent cities and the edges represent the flight segments. We can count the number of segments to determine the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_crdt_document":"","footnotes":""},"categories":[3,4],"tags":[28],"series":[],"class_list":["post-291","post","type-post","status-publish","format-standard","hentry","category-python","category-code","tag-python"],"_links":{"self":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/291","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/comments?post=291"}],"version-history":[{"count":5,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/291\/revisions"}],"predecessor-version":[{"id":301,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/291\/revisions\/301"}],"wp:attachment":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/media?parent=291"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/categories?post=291"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/tags?post=291"},{"taxonomy":"series","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/series?post=291"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}class BreadthFirstSearch:\n def __init__(self):\n self.data = [] #data list from user\n self.edges = [] # convert data list into edges\n self.adj = [] # adjancency matrix\n self.start_node = []\n self.target_node = []\n\n def read(self):\n input = sys.stdin.read()\n self.data = list(map(int, input.split()))\n\n def process_input(self):\n n, m = self.data[0:2]\n self.data = self.data[2:]\n self.edges = list(zip(self.data[0:(2 * m):2], self.data[1:(2 * m):2]))\n self.adj = [[] for _ in range(n)]\n self.start_node = self.data[2 * m] - 1\n self.target_node = self.data[2 * m + 1] - 1\n\n def populate_adjacency_matrix(self):\n for (a, b) in self.edges:\n self.adj[a - 1].append(b - 1)\n self.adj[b - 1].append(a - 1)\n\n def calculate_minimum_nodes_in_path(self):\n self.process_input()\n self.populate_adjacency_matrix()\n \n dist = [-1] * len(self.adj)\n discovered_nodes = queue.Queue()\n discovered_nodes.put(self.start_node)\n dist[self.start_node] = 0\n\n while not discovered_nodes.empty():\n process_node = discovered_nodes.get()\n for next in self.adj[process_node]:\n if next == self.target_node:\n return dist[process_node] + 1\n if dist[next] == -1:\n discovered_nodes.put(next)\n dist[next] = dist[process_node] + 1\n return -1\n\n\nif __name__ == '__main__':\n path_search = BreadthFirstSearch()\n path_search.read()\n print(path_search.calculate_minimum_nodes_in_path())<\/pre>\n","protected":false},"excerpt":{"rendered":"