1

我正在尝试使用 BFS 实现最短路径算法。那就是我试图找到从指定顶点到每个其他顶点的最短路径。但是，它是所有边权重为 1 或 2 的特殊情况。我知道可以使用 Dijkstra 算法完成，但我必须使用广度优先搜索。

到目前为止，我有一个 BFS 的工作版本，它首先搜索与权重为 1 的边相连的顶点。如果找不到，则返回与权重为 2 的边相连的顶点。经过考虑，这不是找到最短路径的正确方法。问题是我想不出任何理由为什么 BFS 会使用权重 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()
   }

那么问题是，我不知道为什么 BFS 可以解决权重为 1 或 2 的最短路径问题，而不是任何权重的任何边缘。

任何帮助表示赞赏。谢谢！

编辑：这是问题所在：您希望找到从 s 到其余顶点的最短路径。这可以使用 Dijkstra 算法完成，但您需要使用广度优先搜索策略。您应该能够做到这一点，因为任何边缘权重都是 1 或 2。描述将解决您的问题的 BFS 更改

4

1 回答 1

1

边权重限制对 BFS 的意义在于，它保证如果从 A 到 B 有一条边，那么从 A 到 B 没有更短的路径。AB 边的最大权重为 2。a 的最小总权重从 A 到 C 到 B 的路径也是 2。

于 2012-12-02T05:35:37.070 回答