Một bác Shipper giao hàng xuất phát từ kho A để lấy hàng và đi giao tất cả các con đường sau đó lại trở về kho A để trả lại những hàng hóa mà khách hàng chưa nhận. Con đường có sơ đồ và thời gian giao hàng (phút) trên mỗi con đường được mô tả trong hình sau:
Thời gian ngắn nhất để bác Shipper hoàn thành công việc trên là bao nhiêu phút?
Sử dụng khái niệm đường đi Euler và thuật toán Dijkstra.
Ta thấy đồ thị trên liên thông (hai đỉnh bất kì đều được nối bằng một đường đi) và có hai đỉnh bậc lẻ là A, D. Do đó, đồ thị có đường đi Euler (đi qua tất cả các cạnh, mỗi cạnh đúng một lần).
Một đường đi Euler qua tất cả các cạnh cần thời gian:
4 + 5 + 17 + 3 + 8 + 8 + 7 + 10 + 9 + 6 + 6 + 10 + 18 + 12 = 123 (phút).
Từ D, cần trở về vị trí ban đầu A. Sử dụng thuật toán Dijkstra tìm được đường đi nhanh nhất là DCBA với 4 + 8 + 10 = 22 (phút).
Vậy thời gian ngắn nhất để Shipper hoàn thành công việc là 123 + 22 = 145 (phút).
Các lý thuyết được ứng dụng:
1. Bậc của đỉnh:
Số cạnh của đồ thị nhận đỉnh làm đầu mút.
2. Đồ thị liên thông:
Hai đỉnh bất kì đều được nối bằng một đường đi.
3. Đường đi Euler:
Đường đi Euler là đường đi qua tất cả các cạnh, mỗi cạnh đúng một lần.
Đồ thị có đường đi Euler không khép kín khi và chỉ khi đồ thị liên thông và có đúng hai đỉnh bậc lẻ.
4. Thuật toán Dijkstra
Bước 1: Gán khoảng cách từ đỉnh nguồn đến chính nó là 0, và đến tất cả các đỉnh khác là vô cùng.
Bước 2: Gọi đỉnh chưa xét với giá trị đánh dấu nhỏ nhất là C.
Bước 3: Với mỗi đỉnh kề (N) với đỉnh hiện tại C và chưa được xét, tính toán khoảng cách mới từ nguồn qua C đến N (bằng khoảng cách của C cộng với trọng số cạnh nối C và N).... Nếu khoảng cách mới này nhỏ hơn khoảng cách hiện đang gán cho đỉnh N, hãy cập nhật lại khoảng cách của N bằng giá trị nhỏ hơn đó.
Bước 4: Đánh dấu đỉnh C là đã xét xong.
Bước 5: Tiếp tục lặp lại bước 2 cho đến khi tất cả các đỉnh đã được xét.
Danh sách bình luận