computer-science - カラーエッジグラフの最短経路

Question

無向および連結グラフでは、各エッジに色（赤、緑、または青）があります。
有効なパスは、各色のエッジが少なくとも1つあるパスです。
問題は、最短の有効なパスを見つける方法、またはパスが存在しないと判断する方法です。

BFSを使おうとしましたが、解決策がわかりませんでした。
始める方法について何かアイデアはありますか？

Answer 1

まず、色数が決まっているとします。次に、O(n log(n) + m) の実行時間をもたらすラベル設定ダイクストラ アルゴリズム (パレート ダイクストラと比較) を提案します。

一般化されたダイクストラを使用して最短パスを見つけます。各ノードにはラベルのリストがあり、1 つのラベルは開始ノードからの長さとまだ訪れたすべての色で構成されます。(1) 長さが短く、(2) 他のラベルのすべての色が含まれます。支配されたラベルは直接削除されます。ダイクストラと同様に、常に長さの短いノードを緩和する優先キューを維持します。ノード v へのエッジを取得すると、ラベルの長さが endge の長さだけ増加し、エッジの色がラベルに追加されます。ノード v のラベルのリストにラベルが追加されます。3 つの色すべてを含むラベルでターゲット ノードを設定すると、最短経路が見つかりました。最後に最短パスを再構築する場合は、各ラベルの先行ノードを保存する必要があることに注意してください。

(0,{}) (長さゼロ、色なし) の開始ノードの初期ラベルから開始します。

この場合、そのような組み合わせは 8 つ (固定) しか存在しないため、各ノードはカラー セットの組み合わせごとに最大 1 回解決できます。最高の実装。

Answer 2

BFS を使用し、各ノードから始めて、そのノードから発見できる最初の有効なパスを計算し、その値を保存して、次のノードに進みます。

グラフは、マトリックス内のエッジの値として各エッジの色 (たとえば、-1 (エッジなし)、0、1、2) を使用して、マトリックスで表すことができます。

発見したパスは、パスのステップを保持する配列と 3 つの色をチェックする配列のペアに入れることができます。

Answer 3

次のような簡単な解決策が存在します。

色がないと仮定して、グラフで通常のダイクストラを実行します。

各色の 3 つのエッジを推測します。すべての m^3 の可能な推測に対して、エッジを r1---r2 、b1---b2、g1---g2 とすると、それらがパスに入る可能性のある 24 の方法が得られます (エッジの向きを設定できる方法については 8 つ) 、順列の場合は 6)。

通常のダイクストラ データは既にあるので、これが完了すると一定時間で結果が得られ、すべての推測が最小化されます。

これを n 個の頂点すべてに対して繰り返します。

最終的な複雑さ O(nm^3) は通常大きすぎることに同意しますが、単純なアルゴリズムが機能する場合もあります。

Answer 4

新しいグラフを作成する (6 回) 元のグラフの 3 つのコピーで構成されます。最初のグラフにはいずれかの色のエッジのみが含まれ、2 番目のグラフには別の色のエッジも含まれ、それらを 2 番目の色のエッジと接続します。 、3 番目のコピーにはすべてのエッジが含まれ、3 番目の色のエッジを持つ 2 番目のグラフに接続されます。次に、dijkstra を実行して、s1 から t3 への最短パスを見つけます。どのような順序になるか分からないので、色の 6 つの可能な順序全体に対して同じことを行い、得られた 6 つの最短パスから最短のものを選択します。