Cùng bài toán nhưng dữ liệu cho bằng BẢNG ma trận khoảng cách

Bước 1 — Đọc dữ liệu.
Ma trận đối xứng: ô hàng $X$ cột $Y$ là khoảng cách $d_{XY}$ (đường chéo bằng $0$, $d_{XY}=d_{YX}$).

Bước 2 — Công thức chu trình.
Với thứ tự thăm $p=(v_1,\dots,v_{n-1})$ xuất phát từ $T$:
$C(p)=d_{Tv_1}+d_{v_1v_2}+\dots+d_{v_{n-1}T}.$ Vì $n$ nhỏ, ta xét mọi thứ tự thăm và lấy giá trị nhỏ nhất.

Bước 3 — Lộ trình tối ưu.
Chu trình ngắn nhất T $\to$ A $\to$ B $\to$ C $\to$ T có chi phí
$d_{TA} + d_{AB} + d_{BC} + d_{CT} = 5 + 6 + 3 + 5 = 19$ km.

Kết luận: tổng quãng đường nhỏ nhất $= 19$ km.