图算法的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