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