0

隣接行列のみを使用してFord-Fulkerson/Edmonds-Karpを実装しようとしています。私がプログラムできないのは、BFSを使用して最短経路を計算する関数だけです。最短経路が実際に存在するかどうかを確認する機能は問題ありませんが、最短経路を取得することもできますか？または、BFSで最短パスを取得して、ある種の親ポインターを使用し、逆方向にトラバースしてパスを取得する唯一の方法はありますか？

パスが存在するかどうかを確認するための私のコードは次のとおりです。

public static boolean existsPathFromSourceToSinkInGf(int Gf[][])
{
    LinkedList<Integer> queue = new LinkedList<Integer>();
    queue.add(0);

    while (!queue.isEmpty())
    {
        int v = queue.remove();
        if (v == sink) return true;
        for (int i = 0; i < 5; i++)
        {

            if (Gf[v][i] != 0)
            {
                if (!queue.contains((Integer)i))
                {
                    queue.add((Integer)i); 
                }
            }
        }
    }

    return false;

  }
4

1 に答える 1

1

それを行う一般的な方法は、実際、ノードを確定するたびに親ポインターを維持し、パスを見つけたら逆方向に移動することです。

キュー内のパスを明示的に追跡することもできます。リンクリストに整数だけを使用する代わりに、整数と「ノード1->ノード3->...」のような文字列で構成される独自のクラスを作成できます。クラスとパスのオーバーヘッドのため、あまり一般的には使用されませんが、親ポインターを独自に保持し、最終的にそれらをトラバースする必要がなくなります。

補足として、コードに関する2つの注意事項：

  1. なぜi=0..5で実行されるのですか？
  2. if (!queue.contains((Integer)i))すでにキューにある頂点をキューに配置しないようにチェックします。また、リストからすでに削除されている頂点を配置することは避けてください（訪問したノードのセットを維持してみてください）。
于 2012-11-16T13:56:52.237 に答える