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)}")