Bước 1 — Mô hình hóa bằng đồ thị.
Coi mỗi phòng là một đỉnh, mỗi cánh cửa là một cạnh nối hai phòng kề nhau với trọng số bằng giá vé. Yêu cầu: xuất phát từ Trung tâm, đi thăm mọi phòng rồi quay về Trung tâm sao cho tổng giá vé nhỏ nhất (mỗi cửa được phép qua lại nhiều lần).
Bước 2 — Đây KHÔNG phải bài "đi qua mọi con đường".
Ta chỉ cần ghé thăm mọi phòng (mọi đỉnh) chứ không bắt buộc đi qua mọi cánh cửa. Vì vậy bài toán là tìm chu trình khép kín ngắn nhất qua tất cả các đỉnh (xuất phát và kết thúc tại Trung tâm), xét trên khoảng cách rẻ nhất giữa các phòng.
Bước 3 — Thử các thứ tự thăm phòng, chọn hành trình rẻ nhất.
Hành trình tối ưu là: Trung tâm $\to$ Khu A $\to$ Khu C $\to$ Khu D $\to$ Khu B $\to$ Trung tâm.
Tổng giá vé $= 150 + 110 + 70 + 130 + 160 = 620$ (nghìn đồng).
Kết luận: số tiền vé ít nhất là $620$ nghìn đồng. Đáp số: $620$.