Khoảng cách ngắn nhất giữa hai đỉnh bằng BFS
Với đồ thị không trọng số, đường đi ngắn nhất không cần thuật toán nặng. Vì mỗi cạnh
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: python-basics, python-lists, python-dicts.
Nội dung đề bài
Mô tả bài toán
Với đồ thị không trọng số, đường đi ngắn nhất không cần thuật toán nặng. Vì mỗi cạnh đều dài đúng bằng 1, duyệt theo tầng bằng hàng đợi là đủ để chạm tới đích với số cạnh ít nhất. Đây là bước mở đầu của mọi bài toán đồ thị, và cũng là bài dễ sai nhất nếu vô tình dùng duyệt sâu: duyệt sâu tìm được một đường đi, nhưng không bảo đảm đó là đường ngắn nhất.
Yêu cầu
Viết hàm shortest_path_length(adj, start, goal) trả về số cạnh ít nhất cần đi để từ đỉnh start tới đỉnh goal. Nếu hai đỉnh không nối được với nhau thì trả về -1.
Quy ước nộp bài
Nộp hàm shortest_path_length trong solution.py. Hệ thống gọi hàm trực tiếp bằng tên đối số adj, start, goal rồi so giá trị trả về; không đọc dữ liệu từ stdin và không in ra stdout.
Input
- adj: danh sách kề của một đồ thị vô hướng gồm n danh sách con; các đỉnh được
đánh số từ 0 đến n - 1 và adj[i] liệt kê các đỉnh kề với đỉnh i.
- start: đỉnh xuất phát, 0 <= start < n.
- goal: đỉnh đích, 0 <= goal < n.
Output
Một số nguyên là số cạnh của đường đi ngắn nhất: 0 khi start == goal, -1 khi không tồn tại đường đi nào.
Ràng buộc
- Số đỉnh n từ 1 đến 8; mỗi danh sách kề tối đa 7 phần tử, không có khuyên và không
lặp cạnh.
- Đồ thị vô hướng: nếu j nằm trong adj[i] thì i cũng nằm trong adj[j].
- Thời gian cần đạt O(n + m) với m là số cạnh; đồ thị có thể chứa chu trình nên phải
đánh dấu đỉnh đã thăm để vòng lặp luôn kết thúc.
Ví dụ 1
Input
shortest_path_length(adj=[[1, 2], [0, 3], [0, 3], [1, 2]], start=0, goal=3)
Output
2
Ví dụ 2
Input
shortest_path_length(adj=[[1], [0, 2], [1, 3], [2, 4], [3]], start=0, goal=4)
Output
4
Giải thích
Với adj = [[1, 2], [0, 3], [0, 3], [1, 2]], start = 0 và goal = 3: tầng đầu tiên gồm 1 và 2, tầng kế tiếp gồm 3, nên hàm trả về 2.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
