C++ Implementation of Graph Algorithm

Question

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

Nothing; I just had a custom queue class lying around that I made for an assignment a year or so ago. It worked perfectly and everything, so I was like, eh, why not? — Edward McGee
– Edward McGee, Commented Oct 22, 2011 at 23:56
I can't understand your for loops, you should have array of all distances not just for one vertex, every time you set distance of nodes to zero in startup, when you are going to get output? write full code (where is your cout?). — Saeed Amiri
– Saeed Amiri, Commented Oct 23, 2011 at 20:03

Salvatore Previti · Accepted Answer · 2011-10-23 02:05:29Z

1

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

edited Oct 23, 2011 at 2:05

answered Oct 23, 2011 at 0:58

Salvatore Previti

9,11033 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Edward McGee Over a year ago

I don't think it's a problem with the used algorithm; I should be able to solve the problem with this algorithm, without having to resort to another. As for the Distance, the edge_distance[][] array returns the distance between any two vertices; the shortest_distance[][] array is what I'm trying to fill using the algorithm (So not just the distance, but the shortest distance).

Collectives™ on Stack Overflow

C++ Implementation of Graph Algorithm

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related