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

Đáp án: $135$ phút 

Giải thích các bước giải:

Tổng trọng số $= 4 + 5 + 17 + 3 + 8 + 8 + 7 + 10 + 9 + 6 + 9 + 10 + 6 + 12 = 114$ phút.
Trong trường hợp này chỉ có một cặp đỉnh bậc lẻ là A và D. Chúng ta sẽ sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ A đến D.

Áp dụng thuật toán Dijkstra từ đỉnh A:

Khởi tạo khoảng cách: dist(A) = 0, dist(X) = vô cùng với X != A.
Tập các đỉnh chưa thăm: {A, B, C, D, E, F, G}.

Bước 1: Chọn đỉnh chưa thăm có khoảng cách nhỏ nhất (A, dist=0). Cập nhật khoảng cách của các đỉnh kề:

dist(B) = min(inf, 0 + 4) = 4
dist(F) = min(inf, 0 + 5) = 5
dist(G) = min(inf, 0 + 17) = 17 Đã thăm: {A}. Chưa thăm: {B, C, D, E, F, G}.
Bước 2: Chọn đỉnh chưa thăm có khoảng cách nhỏ nhất (B, dist=4). Cập nhật khoảng cách của các đỉnh kề:

dist(F) = min(5, 4 + 3) = 5
dist(G) = min(17, 4 + 8) = 12
dist(C) = min(inf, 4 + 8) = 12 Đã thăm: {A, B}. Chưa thăm: {C, D, E, F, G}. dist: A=0, B=4, C=12, D=inf, E=inf, F=5, G=12.
Bước 3: Chọn đỉnh chưa thăm có khoảng cách nhỏ nhất (F, dist=5). Cập nhật khoảng cách của các đỉnh kề:

dist(G) = min(12, 5 + 7) = 12
dist(E) = min(inf, 5 + 10) = 15 Đã thăm: {A, B, F}. Chưa thăm: {C, D, E, G}. dist: A=0, B=4, C=12, D=inf, E=15, F=5, G=12.
Bước 4: Chọn đỉnh chưa thăm có khoảng cách nhỏ nhất (C, dist=12). Cập nhật khoảng cách của các đỉnh kề:

dist(G) = min(12, 12 + 9) = 12
dist(E) = min(15, 12 + 6) = 15
dist(D) = min(inf, 12 + 10) = 22 Đã thăm: {A, B, F, C}. Chưa thăm: {D, E, G}. dist: A=0, B=4, C=12, D=22, E=15, F=5, G=12.
Bước 5: Chọn đỉnh chưa thăm có khoảng cách nhỏ nhất (G, dist=12). Cập nhật khoảng cách của các đỉnh kề:

dist(E) = min(15, 12 + 6) = 15
dist(D) = min(22, 12 + 9) = 21 Đã thăm: {A, B, F, C, G}. Chưa thăm: {D, E}. dist: A=0, B=4, C=12, D=21, E=15, F=5, G=12.
Bước 6: Chọn đỉnh chưa thăm có khoảng cách nhỏ nhất (E, dist=15). Cập nhật khoảng cách của các đỉnh kề:

dist(D) = min(21, 15 + 12) = 21 Đã thăm: {A, B, F, C, G, E}. Chưa thăm: {D}. dist: A=0, B=4, C=12, D=21, E=15, F=5, G=12.
Bước 7: Chọn đỉnh chưa thăm có khoảng cách nhỏ nhất (D, dist=21).
Đã thăm tất cả các đỉnh.

Khoảng cách ngắn nhất từ A đến D tìm được bằng thuật toán Dijkstra là 21 phút.

Thời gian ngắn nhất = Tổng trọng số tất cả các cạnh + Trọng số đường đi ngắn nhất giữa các đỉnh bậc lẻ.
Thời gian ngắn nhất = 114 + 21 = 135 phút.

Thời gian ngắn nhất để bác Shipper hoàn thành công việc trên là 135 phút.