Grafikoni i mrežeSalesman

Do sada smo zanemarili činjenicu da bi neki gradovi mogli biti dalje od ostalih. U stvarnom životu, međutim, ovo je vrlo važno razmatranje: ne želimo samo pronaći bilo koji put, već želimo pronaći najkraći. To se zove Problem prodavca putovanja. To se mora riješiti ne samo u transportu i logistici, već i pri postavljanju tranzistora na mikročipove, radi bržeg računala ili pri analizi strukture DNA.

Jedna jednostavna metoda bilo bi isprobati sve moguće staze, pronalazeći duljinu svakog, a zatim birajte najkraći. Međutim, pokazali smo da čak i sa samo 533 gradova ima ${tsn2}! = ${factorial(tsn2)} mogući putevi. Jednom kada imate stotine ili tisuće vrhova, iskušavanje svih mogućih staza postaje nemoguće, čak i koristeći moćna računala.