与えられた有向加重グラフ G=(V,E)。
負の加重エッジはありません。
各エッジには色が付けられています (黒または黄色)。
指定された s ∈ V の最短パスを見つけるアルゴリズムを見つける必要がありますが、すべてのパスは次のルールに従う必要があります: color(v i ,v i+1 )=color(v i+3 ,v i+4 ), ∀i :1 ≤ i ≤ k-4 パスは v 1 → ... → v kです。アルゴリズムは O(|V|+|E|log(|V|)) である必要があります。
2 に答える
4
ヒント: Dijkstra のアルゴリズムを変更して、2 つの異なる優先度キューを格納してみてください。1 つには、開始ノードから黄色のエッジで終了する宛先ノードへのパスのコストと、開始ノードから宛先へのパスのコストが含まれます。黒いエッジで終わるノード。次に、2 つのキューを考慮するために選択する次のノードを見つけるロジックを更新し、キーの減少ロジックを変更して、正しい情報で適切なキューを更新するようにします。これは、通常のダイクストラのアルゴリズムの定数係数オーバーヘッドのみで実行できるため、O(|E| + |V| log |V|) の時間がかかります。
お役に立てれば！
于 2013-01-02T18:57:29.433 に答える
2
templatetypedef が示唆するように Dijkstra のアルゴリズムを変更するか、グラフを変更して制約に適合させることができます。
色の制約をDFAで認識し、それを加重グラフと組み合わせて、変更されていないダイクストラを適用できるグラフを取得し、典型的なダイクストラ ランタイムを実現できます。
制約の正確なオーバーヘッドは DFA のサイズによって異なりますが、DFA は入力に依存しないため一定です。
于 2013-01-09T13:44:17.063 に答える