图算法的C++实现

Question

我正在尝试实现宽度优先搜索算法，以便找到两个顶点之间的最短距离。我开发了一个队列对象来保存和检索对象，并且我有一个二维数组来保存两个给定顶点之间的边的长度。我试图填充一个二维数组，以保持两个顶点之间的最短距离。

然而，我遇到的问题是，无论我请求的是两个顶点的最短距离，都返回0。这是我算法的实现；如果你能让我走上正确的轨道，帮助我解决我的问题，那就太棒了。

 for (int i = 0; i < number_of_vertex; i++) 
 //For every vertex, so that we may fill   the array
 {
  int[] dist = new int[number_of_vertex]; 
  //Initialize a new array to hold the values for the distances

for (int j = 0; x < number_of_vertex; j++)
{
    dist[j] = -1; 
   //All distance values will be set to -1 by default; this will be changed later on
 }

  dist[i] = 0; //The source node's distance is set to 0 (Pseudocode line 4)

   myQueue.add(i); //Add the source node's number to the queue (Pseudocode line 3)

   while (!myQueue.empty()) //Pseudocode line 5
   {
      int u = myQueue.eject(); //Pseudocode line 6

      for (int y = 0; y < number_of_vertex; y++) //Pseudocode line 7
      {
          if (edge_distance(u,y) > 0)
          {
              if (dist[y] == -1)
              {
                  myQueue.add(y);
                  dist[y] = dist[u] + 1;
                  shortest_distance[i][u] = dist[y];
               }
           }    
        }                 
     }  
}

Answer 1

好的..。我想问题是关于使用的算法和使用的术语。

“为了找到两个顶点之间的最短距离”，你的意思是连通图中两个顶点之间的最短路径？

您要编写的算法是Dijkstra的算法(这是名称)。

http://www.cs.berkeley.edu/~vazirani/algorithms/chap4.pdf