G =（V、E）を無向グラフとし、sとtはVの2つの頂点です。グラフの各エッジは、赤または青に色分けされています。最小数の赤いエッジを持つsとtの間のパスを見つけるアルゴリズムを見つける必要があります。
私は次のアルゴリズムについて考えました：修正されたBFSアルゴリズム
頂点ごとに、「赤レベル」と呼ばれる追加のフィールドを使用します。これは、sからこの頂点へのパス上の赤いエッジの最小数を示します。新しい頂点を発見したら、その赤レベルフィールドを更新します。すでに検出された頂点を探索しようとしている場合、この頂点の赤レベルが現在の赤レベルよりも大きい場合は、この頂点をBFSツリーから削除し、その子を持つ頂点の子として挿入します。現在、探索中などです。目的のパスは、アルゴリズム実行の最後にBFSツリーのsとtを接続するパスです。
私は今、このアルゴリズムが正しいことを証明しようとしていますが、ほとんど成功していません。それが実際に正しいかどうかもわかりません。ヒント/アイデアはありますか？
正しいと思います。基本的に、赤のエッジの重みが非常に大きく、青のエッジの重みが非常に小さいかゼロであるダイクストラのアルゴリズムを実行しています。
残念ながら、アルゴリズムは正しくありません。次のグラフを見てください。G=（V、E）; V = {s、a、b、c、d、e、t}; E = {（s、a）、[s、b]、[s、d]、（a、b）、[b、c]、[d、e]、（c、t）、（e、t） };
（便宜上、（、）を青い無向エッジに、[ 、 ]を赤いエッジにマークしました）
アルゴリズムが「a」の前に「b」を探索することを選択したとします。「s」が終了すると、「a」は赤レベル0になり、「b」と「d」は赤レベル1になります。「d」から探索すると「e」になります。赤レベル2で探索します。「b」から探索します。「s」と「a」は変更されませんが、「c」は赤レベル2になります。次に「a」（BFSによる）を探索します。 'b'の親を'a'に変更し、'b'の赤レベルを0に変更します。この点で、's'から'c'へのパスは正しいが、赤レベルであることに注意してください。 on'c'はそうではありません-それは2の代わりに1であるはずです。今、私たちは進み続け、'e'からecploreします（'s'とその直接の子'a'、' b'、および'd'）：エッジ（e、t）で「t」が検出されるため、「t」は赤レベル2になります。エッジ（e、d）は何も変更しません。ここで、クールな部分に到達します。「c」から探索します。エッジ（c、b）は何も変更しませんが、エッジ（c、t）はどうでしょうか。「t」は（「e」から）すでに検出されているため、アルゴリズムに従って、レッドレベルに違いがある場合にのみ何かを変更します。しかし、「c」の赤レベルは2であるため、ありません（誤って！）。したがって、「t」の親は「e」のままであり、「s」からのパスには2つの赤いエッジが含まれますが、「s」から「t」へのパスには1つの赤いエッジのみが含まれます：s-> a-> b-> c-> t エッジ（c、b）は何も変更しませんが、エッジ（c、t）はどうですか？「t」は（「e」から）すでに検出されているため、アルゴリズムに従って、レッドレベルに違いがある場合にのみ何かを変更します。しかし、「c」の赤レベルは2であるため、ありません（誤って！）。したがって、「t」の親は「e」のままであり、「s」からのパスには2つの赤いエッジが含まれますが、「s」から「t」へのパスには1つの赤いエッジのみが含まれます：s-> a-> b-> c-> t エッジ（c、b）は何も変更しませんが、エッジ（c、t）はどうですか？「t」は（「e」から）すでに検出されているため、アルゴリズムに従って、レッドレベルに違いがある場合にのみ何かを変更します。しかし、「c」の赤レベルは2であるため、ありません（誤って！）。したがって、「t」の親は「e」のままであり、「s」からのパスには2つの赤いエッジが含まれますが、「s」から「t」へのパスには1つの赤いエッジのみが含まれます：s-> a-> b-> c-> t