Đồ thị và Mạng lướiSalesman

Cho tới lúc này chúng ta đã bỏ qua thực tế là một số thành phố có thể xa nhau hơn những thành phố khác. Trong ứng dụng thực tế xem xét điều này là rất quan trọng: vì chúng ta không chỉ muốn tìm đường đi bất kỳ mà là đường đi ngắn nhất. Bài toán này được gọi là Bài toán vận chuyển của người bán hàng. Bài toán này phải được giải không chỉ cho việc vận chuyển và hậu cần (logistics), mà có liên quan đến việc lắp đặt linh kiện bán dẫn và microchips, để làm cho máy tính nhanh hơn, hay được sử dụng để phân tích cấu trúc của DNA.

Một phương pháp đơn giản là tìm tất cả các đường đi có thể có, tìm độ dài đường đi của mỗi con đường và chọn ra phương án đi ngắn nhất. Tuy nhiên ta vừa thấy rằng, duy với ${tsn2} thành phố đã có ${tsn2}! = ${factorial(tsn2)} con đường khác nhau. Một khi bạn có hàng trăm hay hàng ngàn đỉnh, việc tìm kiếm các con đường khác nhau là bất khả thi, ngay cả khi bạn dùng máy tính mạnh nhất.