prev là đỉnh phát hiện, không phải đỉnh đứng ngay trước trong order
Trong BFS mẫu, prev[5]=3, prev[3]=1, prev[1]=0. Lần ngược từ 5 nhận [5,3,1,0]; đảo lại được [0,1,3,5]. Mỗi cặp liên tiếp phải có cạnh nối đúng chiều.
Không lấy đoạn của danh sách order làm đường đi: order chỉ là thứ tự xử lí, hai đỉnh liên tiếp trong đó chưa chắc kề nhau. Nguồn s có prev[s]=None nhưng vẫn tới được chính nó với khoảng cách 0; vì vậy dùng dist hoặc seen để xét có đường, không chỉ kiểm prev[t].
Trả danh sách đỉnh của một đường ít cạnh nhất
shortest_path trả [] khi không tới được; nếu s=t, trả [s]. path_by_name là phần vận dụng nhập tên; giả định names có đúng một tên riêng cho mỗi đỉnh và thứ tự khớp chỉ số.
```python
def shortest_path(Adj, s, t):
check_vertex(Adj, s)
check_vertex(Adj, t)
order, dist, prev = bfs(Adj, s)
if dist[t] == -1:
return []
path = [t]
while path[-1] != s:
path.append(prev[path[-1]])
path.reverse()
return path
def path_by_name(Adj, names, start, finish):
if start not in names or finish not in names:
raise ValueError("Tên không có trong danh sách")
return shortest_path(Adj, names.index(start), names.index(finish))
```
Chạy xe_dap.py bằng dữ liệu giả định
Trong bộ mẫu, ten_nha.inp có bảy nhãn Nhà mẫu A,…,Nhà mẫu G, theo chỉ số 0,…,6. canh.inp mô tả các tuyến hai chiều được phép đi xe đạp. Đây chỉ là mô hình học thuật, không là chỉ dẫn giao thông thật.
Chạy xe_dap.py; nhập `0 5` để nhận **Nhà mẫu A → Nhà mẫu B → Nhà mẫu D → Nhà mẫu F**, số cạnh 3. Nhập `0 6` phải báo không có đường. Nhập `2 2` phải cho Nhà mẫu C, số cạnh 0. Chương trình nhận cả s>t, chẳng hạn `5 0`; nhập q để thoát. Chỉ số ngoài 0,…,6 hoặc thiếu hai số được báo không hợp lệ.
Nếu cần tra bằng tên trong mã, gọi path_by_name(Adj,names,'Nhà mẫu A','Nhà mẫu F'). Kiểm tên có trong danh sách trước khi tìm chỉ số để tránh nhầm tên không tồn tại. Thay đổi thứ tự kề có thể chọn một đường ít cạnh nhất khác nếu có nhiều đường cùng độ dài.
Bài luyện
Vì sao prev[s]=None không có nghĩa không tồn tại đường từ s đến s?
None không đại diện một đỉnh.
Không cần khuyên để có đường độ dài 0.
Đúng. Cần xét dist[s]=0 hoặc seen[s].
Đồ thị có thể không liên thông.
Lời giải
BFS khởi tạo nguồn có khoảng cách 0 và đã được đánh dấu. Nguồn không có đỉnh phát hiện trước nó nên prev[s]=None. shortest_path vẫn trả [s] khi nguồn trùng đích.
Bài luyện
prev[5]=3, prev[3]=1, prev[1]=0, nguồn 0. Đường dựng lại là gì?
Đúng. Lần ngược rồi đảo kết quả.
Đây là chiều lần ngược, cần đảo để đi từ nguồn.
Các đỉnh liên tiếp trong order chưa chắc có cạnh.
Không được bỏ các đỉnh trung gian cần thiết.
Lời giải
Bắt đầu ở đích 5, lần prev về 3,1,0 tạo [5,3,1,0]. Đảo danh sách được [0,1,3,5], gồm các cạnh 0–1,1–3,3–5.
Bài luyện
shortest_path mẫu từ 0 đến 6 trả gì?
Không có cạnh hoặc đường nối tới 6.
[6] chỉ đúng nếu nguồn cũng là 6.
[0] chưa tới đích 6.
Đúng. dist[6]=−1 nên không có đường.
Lời giải
6 biệt lập nên BFS từ 0 không phát hiện 6, dist[6] vẫn −1. Hàm dùng [] làm kết quả không có đường; không thêm một cạnh giả từ 0 tới 6.
Đang học