Egy majdnem gyakorlati probléma.

Külföldi nyaralásra készülünk bérautóval. Meg szeretnénk nézni n várost, és ismert közülük bármely (i-edik) város bármely (j-edik) másiktól vett d_ij=d_ji távolsága (e szempontból a városok legyenek pontszerűek). Itthonról (az n közül) egy bizonyos A városba érkezünk (ott bérelünk autót) és ugyanonnan indulunk majd haza.
Hogyan találjuk meg azt a legrövidebb útvonalat, amely A-ból indul, A-ba érkezik és amely mentén mind az n várost legalább egyszer érintjük?

(Az idő, az üzemanyag és egyéb erőforrások korlátlannak tekintendők.)

Legyen pl. n=7, az A város a 2-es és a d_ij=d_ji értékek az ábra szerintiek.