優先順位グラフの最短経路

Question

私は、接続グラフを考慮して優先順位グラフの最短経路を決定するアルゴリズムを探しています。私はDijkstraとBellman Fordを調べましたが、すべての頂点で1つのエッジだけ外に出ているので、優先順位グラフのために実行可能であるとは思いません。 しかし、優先順位グラフでは、次の頂点に到達するために2つ以上の辺を通過する必要がある場合もあります。たとえば、分解するためには部品Aと部品Bを最初に取り外す必要がありますので、部品Cに届きます。

私が解決しようとしているもの： 製品をどのように分解するかを表す単純な優先順位グラフがあります。すべての頂点にはコスト（時間単位）があります。このグラフで私は出発地と目的地を持っています。結果は、分解に必要な最短時間でなければなりません。

また、接続グラフに応じて特定の部分に到達するために、全体としてmoulesを逆アセンブルすることもできます。このグラフは、部品が実際にどのように相互に接続されているかを示しています。 A、B、Cと同様にDに到達するには削除する必要があります.Aは最初に削除する必要があります。次に、BとCを全体として削除することができます（Bがまだそれに付いている間にCを削除します）。

Answer 1

私は最初の部分のために私の目的に合うようにいくつかの変更を加えてDeep-first検索アルゴリズムを使用しました。第2の部分は、モジュールが1つの平和の代わりに分解されるとみなされるべきであり、依然として欠けている。たぶんアルゴリズムにいくつかの変更を加えても可能です。