最短の色のパスを見つけるには？

Question

与えられたG =（V、E）各エッジは、これらの3つの色{緑、赤、青}のうちの1つを有する。 3つの色がすべて入っている場合は、「色付きパス」というパスを呼び出します。

Input: graph G(V,E),weight function w:E->Q+ , colored edges and vertices s . 
    output: algorithm that finds for every vertices v, a shortest path from s 
      that is Colored path 

解決方法私の解決策は、グラフを歩き回り、すべての頂点にパスの色数を数えることです。 G1、G2、G3という名前のグラフを3つ作成する

c（v）= 2（cはsからこのパスまでの色数）の2番目のグラフ（G2）のv2に接続するすべてのエッジc（v）= 3について、エッジ重み= 0でv2（G2から）からv3（To G3）に接続する。

dijkstraをsからt3（G3）に実行します。

私の解決策は正しいですか？

Answer 1

私には正しくありません。

最も簡単な方法は、通常のダイクストラでは、各ノードに格納する重要なものは1つだけで、ルートからの絶対最短パス長です。

色付きのパスでは、すべての色の組み合わせに対して最短パスの長さを保存する必要があります。したがって、3色の場合、最短の赤色のパス、最短の青色のパス、最短の緑色のパス、最短の赤青、赤緑、青緑のパス、最後に最短赤緑-blueパス。 （合計7色の組み合わせ）。