Sono date 4 città A, B, C, D e le distanze che le separano attraverso un collegamento diretto sono espresse dalla seguente matrice quadrata:
A B C D A 0 5 4 3 B 5 0 1 2 C 4 1 0 3 D 3 2 3 0 Ad esempio
- l’elemento di riga A e colonna B esprime il fatto che la distanza fra A e B utilizzando il collegamento diretto fra le città è pari a 5;
- analogamente si può verificare che la distanza del collegamento diretto fra D e C è pari a 3.
Qual è la lunghezza complessiva del percorso più breve che partendo da A visita tutte le altre città senza passare nuovamente per A?
Ad esempio,
- se andiamo da A a B e poi da B a C e infine da C a D, la lunghezza complessiva del percorso è pari a 9
infatti 5, 1 e 3 sono le distanze dei tre collegamenti.