Lekcja – Najkrótsza ścieżka BFS
V = { 'P' : ['D1','D2','K', 'Q', 'H'], 'D1': ['P','D2','E'], 'D2': ['P','D1'], 'K' : ['P', 'Q'], 'Q' : ['P', 'K', 'H'], 'H' : ['P', 'Q'], 'E' : ['D1'] } def is_path_between(V, source, dest): list_to_check = [[source]] list_visited = [] while list_to_check: current_path = list_to_check.pop(0) current_node = current_path[-1] if current_node == dest: return current_path else: if current_node not in list_visited: list_visited.append(current_node) for n in V[current_node]: new_path = current_path.copy() new_path.append(n) list_to_check.append(new_path) return [] for s in V.keys(): for d in V.keys(): if s != d: print(f'Connection {s} - {d} - {is_path_between(V, s, d)}')
Lab
import csv network = {} select_month = 1 with open('data/usa-domestic-flight-2019.csv') as csv_file: csv_reader = csv.reader(csv_file, delimiter=',') line_count = 0 for row in csv_reader: if line_count == 0: print(f'Column names are {", ".join(row)}') line_count += 1 else: line_count += 1 origin = row[8] destination = row[11] month = int(row[12]) if month != select_month:# or passengers == 0: continue if origin not in network.keys(): network[origin] = [destination] else: if destination not in network[origin]: network[origin].append(destination) current_keys = list(network.keys()) for origin in current_keys: for destination in network[origin]: if destination not in network.keys(): network[destination] = [] print(f'Processed {line_count} lines.') #print(network.keys()) def is_path_between(V, source, dest): list_to_check = [[source]] list_visited = [] while list_to_check: current_path = list_to_check.pop(0) current_node = current_path[-1] if current_node == dest: return current_path else: if current_node not in list_visited: list_visited.append(current_node) for n in V[current_node]: new_path = current_path.copy() new_path.append(n) list_to_check.append(new_path) return [] start = 'San Francisco, CA' stop = 'Vernal, UT' print(f"connection from {start} to {stop}: {is_path_between(network, start, stop)}") start = 'Vernal, UT' stop = 'San Francisco, CA' print(f"connection from {start} to {stop}: {is_path_between(network, start, stop)}") start = 'Kotzebue, AK' stop = 'Danger Bay, AK' print(f"connection from {start} to {stop}: {is_path_between(network, start, stop)}") start = "New Stuyahok, AK" stop = "Gallup, NM" print(f"connection from {start} to {stop}: {is_path_between(network, start, stop)}")