图算法的C++实现

Question

我正在尝试实现 Breadth-first search algorithm , 为了找到两个顶点之间的最短距离。我开发了一个 Queue 对象来保存和检索对象，并且我有一个二维数组来保存两个给定顶点之间的边的长度。我正在尝试填充二维数组以保持两个顶点之间的最短距离。

然而，我遇到的问题是，无论我请求哪两个顶点的最短距离，都返回 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