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 shortest distance.
The following can be applied to any situation in finding the shortest path. It is an implementation of the breadth first search algorithm.
See code below.
Problem: 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).
Input Format: An undirected graph with n vertices and m edges. The next line contains two vertices u and v of the graph.
Constraints: 2 ≤ n ≤ 10^5 , 0 ≤ m ≤ 10^5 , u 6 = v, 1 ≤ u, v ≤ n.
Result: Integer value of the minimum number of edges in a path from u to v, or −1 if there is no path.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
class BreadthFirstSearch: def __init__(self): self.data = [] #data list from user self.edges = [] # convert data list into edges self.adj = [] # adjancency matrix self.start_node = [] self.target_node = [] def read(self): input = sys.stdin.read() self.data = list(map(int, input.split())) def process_input(self): n, m = self.data[0:2] self.data = self.data[2:] self.edges = list(zip(self.data[0:(2 * m):2], self.data[1:(2 * m):2])) self.adj = [[] for _ in range(n)] self.start_node = self.data[2 * m] - 1 self.target_node = self.data[2 * m + 1] - 1 def populate_adjacency_matrix(self): for (a, b) in self.edges: self.adj[a - 1].append(b - 1) self.adj[b - 1].append(a - 1) def calculate_minimum_nodes_in_path(self): self.process_input() self.populate_adjacency_matrix() dist = [-1] * len(self.adj) discovered_nodes = queue.Queue() discovered_nodes.put(self.start_node) dist[self.start_node] = 0 while not discovered_nodes.empty(): process_node = discovered_nodes.get() for next in self.adj[process_node]: if next == self.target_node: return dist[process_node] + 1 if dist[next] == -1: discovered_nodes.put(next) dist[next] = dist[process_node] + 1 return -1 if __name__ == '__main__': path_search = BreadthFirstSearch() path_search.read() print(path_search.calculate_minimum_nodes_in_path()) |
Leave a Reply