私はいくつかのアプローチを試みましたが、それらはすべて行き止まりに終わりました。質問：
G=(V,E) が与えられた場合、すべての頂点が赤または青に着色された重み付けされていない有向グラフ。V から頂点 s と t があるとします。s と t の間で最も赤い頂点を保持しないパスを見つけるアルゴリズムを説明してください。アルゴリズムを説明し、証明し、その複雑さを示します。
私は2つのアプローチを考え、両方を破棄しました:
正しい方向への助けをいただければ幸いです。完全な回答ではなく、ヒット/ヒントを得ることを好みます。
この質問に対する答えを見つけたのは、私ではなく私の友人でした。
BFS アルゴリズムで 1 つのキューを使用する代わりに、2 つのキューを使用します。1 つは青色の頂点用、もう 1 つは赤色の頂点用です。
S の色を確認し、それを正しいキューに追加します。青い頂点のキューが空でない限り、そこからデキューし、通常の BFS を続行します。赤い頂点に遭遇した場合は、それを赤いキューにキューに入れます。青い頂点を見つけて、それを青いキューに入れます。青のキューが空の場合、赤のキューからデキューします。
最終的に、配列 pi[|V|] は、赤い頂点が最も少ない頂点 v への後方表現を保持します。
BFSアルゴリズムには実際の変更はなく、そのデータ構造には変更がないため、正確性の証明が保持され、時間の複雑さはBFSのようにO（| V | + | E |）です。
助けてくれてありがとう！
赤い頂点に向かうエッジには weight=1 を設定することを検討してください。次に、s からn 個の赤い頂点を持つパスのコストが、s の色に応じてnまたはn-1であることを示します。