1

BFS を使用して最短パス アルゴリズムを実装しようとしています。つまり、指定された頂点から他のすべての頂点への最短経路を見つけようとしています。ただし、すべてのエッジの重みが 1 または 2 の特殊なケースです。ダイクストラのアルゴリズムで実行できることはわかっていますが、幅優先探索を使用する必要があります。

これまでのところ、重み 1 のエッジに接続された頂点を最初に検索する BFS の作業バージョンがあります。それが見つからない場合は、重み 2 のエッジに接続された頂点を返します。最短経路を見つける正しい方法。問題は、BFS がウェイト 1 または 2 ではなく、ウェイト 1 または 2 で機能する理由が思いつかないことです。

コードは次のとおりです。

public void addEdge(int start, int end, int weight)
  {
  adjMat[start][end] = 1;
  adjMat[end][start] = 1;
  edge_weight[start][end] = weight; 
  edge_weight[end][start] = weight; 
  }

// -------------------------------------------------------------
public void bfs()                   // breadth-first search
  {                                // begin at vertex 0
  vertexList[0].wasVisited = true; // mark it
  displayVertex(0);                // display it
  theQueue.insert(0);              // insert at tail
  int v2;

  while( !theQueue.isEmpty() )     // until queue empty,
     {
     int v1 = theQueue.remove();   // remove vertex at head
     // until it has no unvisited neighbors
     while( (v2=getAdjUnvisitedVertex(v1)) != -1 ){// get one,
        vertexList[v2].wasVisited = true;  // mark it
        displayVertex(v2);                 // display it
        theQueue.insert(v2);               // insert it
        }
     }  // end while(queue not empty)

  // queue is empty, so we're done
  for(int j=0; j<nVerts; j++)             // reset flags
     vertexList[j].wasVisited = false;
  }  // end bfs()
// -------------------------------------------------------------
// returns an unvisited vertex adj to v -- ****WITH WEIGHT 1****
public int getAdjUnvisitedVertex(int v) {
    for (int j = 0; j < nVerts; j++)
        if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false && edge_weight[v][j] == 1){
            //System.out.println("Vertex found with 1:"+ vertexList[j].label);
            return j;
        }
    for (int k = 0; k < nVerts; k++)
        if (adjMat[v][k] == 1 && vertexList[k].wasVisited == false && edge_weight[v][k] == 2){
            //System.out.println("Vertex found with 2:"+vertexList[k].label);
            return k;
        }
    return -1;
}  // end getAdjUnvisitedVertex()
   // -------------------------------------------------------------
}  
////////////////////////////////////////////////////////////////
public class BFS{
public static void main(String[] args)
  {
  Graph theGraph = new Graph();
  theGraph.addVertex('A');    // 0  (start for bfs)
  theGraph.addVertex('B');    // 1
  theGraph.addVertex('C');    // 2

  theGraph.addEdge(0, 1,2);     // AB
  theGraph.addEdge(1, 2,1);     // BC
  theGraph.addEdge(2, 0,1);     // AD


  System.out.print("Visits: ");
  theGraph.bfs();             // breadth-first search
  System.out.println();
  }  // end main()
   }

問題は、任意の重みのエッジではなく、重み 1 または 2 のエッジを使用した最短経路問題に対して BFS が機能する理由がわからないことです。

どんな助けでも大歓迎です。ありがとう！

編集:ここに問題があります: s から残りの頂点までの最短経路を見つけたいと考えています。これは、ダイクストラのアルゴリズムを使用して行うことができますが、幅優先探索戦略を使用する必要があります。辺の重みは 1 または 2 であるため、これを実行できるはずです。問題を解決する BFS の変更について説明してください。

4

1 に答える 1

1

BFS に対するエッジの重み制限の重要性は、A から B へのエッジがある場合、A から B へのより短いパスが存在しないことを保証することです。AB エッジの最大重みは 2 です。 A から C から B へのパスも 2 です。

于 2012-12-02T05:35:37.070 に答える