Đường đi ngắn nhất III
Đây là bài cuối cùng trong bộ ba! Giờ bạn sẽ hoàn thiện bài toán bằng cách viết mã trả về False nếu không có đường đi giữa hai nút.
Bài tập này là một phần của khóa học
Nhập môn Phân tích Mạng bằng Python
Hướng dẫn bài tập
- Kiểm tra xem hàng đợi đã trống chưa. Bạn có thể làm điều này bằng cách xem phần tử cuối của hàng đợi với
[-1]. - Đặt câu lệnh
returnphù hợp để cho biết có hay không có đường đi giữa hai nút này.
Bài tập tương tác thực hành trực tiếp
Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.
def path_exists(G, node1, node2):
"""
This function checks whether a path exists between two nodes (node1, node2) in graph G.
"""
visited_nodes = set()
queue = [node1]
for node in queue:
neighbors = list(G.neighbors(node))
if node2 in neighbors:
print('Path exists between nodes {0} and {1}'.format(node1, node2))
return True
break
else:
visited_nodes.add(node)
queue.extend([n for n in neighbors if n not in visited_nodes])
# Check to see if the final element of the queue has been reached
if node == ____:
print('Path does not exist between nodes {0} and {1}'.format(node1, node2))
# Place the appropriate return statement
return ____