CODEWITHSUNDEEP
c++graphbreadth-first-search
Edward McGee
Edward McGee

Reputation: 29

C++ Implementation of Graph Algorithm

I am trying to implement the Breadth-first search algorithm, in order to find the shortest distance between two vertices. I have developed a Queue object to hold and retrieve objects, and I have a two-dimensional array to hold the length of the edges between two given vertices. I am attempting to fill a two-dimensional array to hold the shortest distance between two vertices.

The problem I am having, however, is that no matter what two vertices I request the shortest distance of, 0 is returned. Here is my implementation of the algorithm; if you can set me on the right track and help me figure out my problem, that would be fantastic.

 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];
               }
           }    
        }                 
     }  
}

Upvotes: 1

Views: 2022

Answers (1)

Salvatore Previti
Salvatore Previti

Reputation: 9050

Ok... i guess the problem is about the used algorithm and about used terms.

"In order to find the shortest distance between two vertices" you mean the shortest path between two vertices in a connected graph?

The algorithm you are trying to write is the Dijkstra's algorithm (this is the name).

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

Upvotes: 1

Related Questions