





|
|
Das bekannteste Problem dieser Klasse ist das Travelling Salesman-Problem (TSP). Dabei muss in einem Netz von Städten die schnellste oder kostengünstigste Route zwischen zwei oder mehreren Städten gefunden werden.
Dazu werden die Kanten des Graphen gewichtet (bewertet), damit die Kosten für jeden Pfad kalkuliert werden können
.

bewerteter Graph
|