iが解決しようとしている問題に最もカラフルなパスを検索すると、このです：グラフG =（V、E）が与えられるグラフ
毎エッジは、10色のうちの一つで着色し、そしてするよう2つの頂点：s、t。
sからtまでの（最短）パスを生成するアルゴリズムを見つける必要があります。これは、最小限の色を使用します。
私の考えは、グラフを複製することだった10回：
最初の重複は、第二のように... 2色の端のみを含めるとなり一色
のエッジのみが含まれます。
また、私は外側のノード：s 'を各複製のすべての "s"ノードに接続します。
しかし、このアプローチでは、グラフを10回ではなく10回くらい複製する必要があります。 （あるいは多分2^10？）回の色のすべての組み合わせに対して。
これを解決するための効率的なアルゴリズムは何でしょうか？
編集： 以下の方法は、ポールによって提案されているように動作しません。
このアプローチを試してみてください。正しいかどうかはわかりません。
同じ色で同じエッジを共有するノードをマージすることから始めます。これは、uとvの両方が異なる色を持つエッジ（u-> v）のみを含むグラフを縮小します。
この後、グラフのすべてのエッジに一定の重みを与えます。 グラフ上でdijkstraを実行し、訪問した色を追跡し、新しい色を訪れるたびに、訪問されたノードから使用されていない色のセットにない新しい高い重みで未訪問のグラフ全体を更新します。
誤解を招いて申し訳ありませんが、あなたは編集を見たことがありますか？ –
これは動作しません（私の答えにコメントを参照してください）。 – Paul
@Paulに同意すると動作しません。 Dijkstraのアルゴリズムの一般化を使用する場合、異なるサブセットの色を使ってノードへの最短経路を追跡する必要があります。 –
問題の一般的な形式がNP困難なので、これを解決する簡単なアルゴリズムはないと思います。つまり、任意の色のグラフで、最小限の色のセットに接触する2つの頂点間の最短経路を見つけることは、NP困難です。
このように、わずかに優れたアルゴリズムがありますが、グラフの1024種類（10種類の色のサブセットごとに1種類）の問題を解決するという考え方は妥当と思われます。
証拠は、それに当たっ設定の問題を減らすことによって動作します。ヒットセットの問題はNP完全なので、あなたの問題を軽減すると、問題はNP困難であることが示されます。
ヒットセットの問題は、それぞれがある宇宙Uの要素を持つ集合X1 ... Xnをとり、すべてのiに対して最小集合{x1、...、xk} ajであり、Xiのxjである。
グラフの色はUの要素になります。グラフ自体はn + 1個の頂点で構成されます。これらはX0（以下の表記上の便宜のためにのみ命名された開始ノード）とX1 ... Xnを表す頂点になります。
Xi + 1の各xについて、XiをXi + 1に色xのエッジで接続します。
このグラフでは、X0からXnまでのすべてのパスの長さはnですが、最小限の色数を使用するパスは、正確には最小のヒットセットに相当します。
ノードの間に複数のエッジを含むように、グラフの定義を拡張することに注意してください。そうでない場合は、構築されたグラフの各辺の中央に余分なノードを追加します。
教育のお返事ありがとうございます！つまり、（可能な限り複雑な）アルゴリズムを考えることができますか？ –
@wannabeprogrammer可能な最善の複雑さは知られていません（それはP = NPを証明するか反証するので）。だからいいえ:) –
どのようなアルゴリズムは？ 1024のグラフの複製と言うのですか？ –
さらに重要な、最短または最小の色は何ですか？トレードオフは可能ですか（たとえば、もう1つの色が2つのエッジを構成します...）。 – Henry
最小限の色が重要です。むしろ、別の色を追加するよりもパスを長くしています。 –
問題の原因を共有することができます –