Un autre problème classique de théorie des graphes est celui du voyageur de commerce : les nœuds du graphe sont un ensemble de villes ou de clients à livrer tandis que les arêtes sont les infrastructures routières, munies d’un poids modélisant la distance associée. On cherche à desservir toutes les villes en empruntant le chemin le plus court.