義務的なノードを通過させた有向グラフの最短経路

Question

こんにちは私はこの問題を解決するための最良のアルゴリズムを見つけようとしています。

私は、指定された開始ノードと終了ノードの間の最短経路を見つけなければならないが、特定のユーザ入力ノードを通過しなければならないというグラフがある。

必須のノードがないため、各ノードに複数回アクセスすることはできません。

私は各ノードが特定の順序で到達する必要があると考えている場合、最初に各停止までの最短経路を計算するのが簡単でしょうか？

K最短経路はこの問題を解決する方法ですか？最短の経路を計算し、そこから進み、すべてがノードを通過する必要がある最短経路を見つけるまで、ここ

iが

ノード4及び6を通過しなければならないし、そして私はそれが十分2つの互いに素な経路問題ことが知られている1および5

Answer 1

間の最短経路を見つける必要が描く例示的グラフです。 NP-complete in digraphsです。それらの証明はグラフGと2つのソース頂点s1、s2と2つの端子t1、t2を有する。タスクは、2つの内部的に頂点のある離散パスp1、p2を見つけることです。p1はs1をt1に接続し、p2はs2、t2を接続します。私たちは、単に離れた経路であなたの問題をモデル化することができます。上記の硬さ証明で提供されるグラフでは、単にs2、t1を識別し、それを新しい頂点s2t1にします。次に、s1で始まるパスがs2t1を通り、t2で終わる場合にのみ、元のグラフに2つの互いに素なパスがあります。これは、有向グラフでそのようなパスを見つけることさえ難しいことを意味します。最適化バージョンでさえありません。

しかし、グラフに特殊な構造があれば、それはより簡単になります。例えばのように。非循環グラフではより簡単です。