Đường đi ngắn nhất
Bài học 12 trên 14 trong khóa học Đồ thị, chuỗi cấu trúc dữ liệu #9 của Coddy.
Cần ít nhất bao nhiêu cạnh để đi từ start đến end? Trong đồ thị không trọng số, tức là mọi cạnh đều có cùng chi phí, đáp án chính là kết quả BFS tính được. Vì BFS duyệt các đỉnh theo thứ tự khoảng cách tăng dần tính từ đỉnh bắt đầu, lần đầu tiên ta đến end là theo một đường đi ngắn nhất.
Mẹo là đưa mỗi đỉnh vào hàng đợi cùng với khoảng cách tính đến lúc đó. Bắt đầu với (start, 0). Mỗi khi tìm thấy một đỉnh kề mới v từ một đỉnh có khoảng cách d, hãy đưa (v, d + 1) vào hàng đợi. Khi v == end, hãy trả về d + 1.
Có hai trường hợp đặc biệt. Nếu start == end, đáp án là 0. Nếu BFS kết thúc mà chưa từng đến end, hai đỉnh nằm trong các thành phần liên thông khác nhau, và đáp án là -1.
Thử thách
DễViết một hàm (function) shortestPath nhận một mảng số nguyên 2 chiều adjacency, một số nguyên start và một số nguyên end, rồi trả về khoảng cách ngắn nhất (số cạnh) từ start đến end.
- Nếu
start == end, trả về0. - Nếu không thể đi từ
startđếnend, trả về-1. - Nếu không, trả về số cạnh ít nhất giữa hai đỉnh.
Bạn phải dùng lớp Graph (được cung cấp trong graph), không dùng kiểu dữ liệu dựng sẵn của ngôn ngữ (bản đồ, tập hợp) để mô hình hóa danh sách kề. Dữ liệu phụ trợ cho thuật toán (tập hợp các đỉnh đã thăm, hàng đợi) có thể dùng các kiểu dữ liệu trong thư viện chuẩn.
Tự làm thử
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start, end;
if (scanf("%d %d %d %d", &n, &m, &start, &end) != 4) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%d\n", shortestPath(adjacency, m, start, end));
return 0;
}
Tất cả bài học trong Đồ thị, chuỗi cấu trúc dữ liệu #9
Tự luyện tập: Trình biên dịch C online