Finde den kürzesten Pfad in einem gerichteten Graphen, der durch bestimmte Ecken verläuft

Question

Es gibt einen gewichteten gerichteten Graphen. Wie man den kürzesten Pfad im gerichteten Graphen erhält, der durch bestimmte Ecken verläuft.

Answer 1

Tatsächlich fällt dieses Problem in die Klasse von NP, weil der Hamiltonsche Weg, das wohlbekannte NP-Problem, auf dieses Problem reduziert werden kann. Sie können also Brute-Force-Suche oder einen Approximationsalgorithmus verwenden.