finding shortest path of unweighted node in c++

[hawkeyeviewonu]

Sorry for my english..
Im trying to make a program that show the shortest route of this nodes using BFS algorithm..

i tried to print the prev array which shows the shortest route but somehow it doesnt appear on console when running..
how to fix it?

btw, is there any much simple algorithm than these one?
thanks.

>  #include <stdio.h>
>  #include <queue>
>  #include <conio.h>
>  using namespace std;
> 
>  int nodes, edges, src, dest;
>  int graph[100][100], color[100],distance[100],prev[100];
>  const int WHITE = 0;
>  const int GRAY = 1;
>  const int BLACK = 2;
> 
>  int main() {
>      printf("Nodes, edges, source, destination? ");
>      scanf("%d %d %d %d", &nodes, &edges, &src, &dest);
>      for (int i = 1; i <= edges; i++) {
>          printf("Edge %d: ", i);
>          int x, y;
>          scanf("%d %d", &x, &y);
>          graph[x][y] = 1;
>      }
> 
>      //run BFS
>      queue<int> q;           //create a queue
>      q.push(src);            //1. put root node on the queue
>      do {
>          int u = q.front();  //2. pull a node from the beginning of the queue
>          q.pop();
>          printf("%d ", u);   //print the node
>          for (int i = 1; i <= nodes; i++) {  //4. get all the adjacent nodes
>              if ((graph[u][i] == 1)  //if an edge exists between these two nodes,
>                  && (color[i] == WHITE)) {   //and this adjacent node is still WHITE,
>                  q.push(i);                  //4. push this node into the queue
>                  color[i] = GRAY; prev[i] = u;            //color this adjacent node with GRAY
>              }
>          }
>          color[u] = BLACK;   //color the current node black to mark it as dequeued
>      } while (!q.empty());   //5. if the queue is empty, then all the nodes have been visited
>          for(int i=10;i<=0; i--)
>             {if (prev[i] == 0)
>             {            }
>             else
>             printf("%d -> ", prev[i]); }
>      getch();
>      return 0;
>  }
> 

[histrungalot]

I didn't look all of it but on line 38 is one of your issues.

// The check on i is not correct, it will never 
// enter the loop
for(int i=10;i<=0; i--)
// It should be i greater than or equal 
for(int i=10;i>=0; i--)

[histrungalot]

Two more things.

1.When defining the edges you have to set both graph[x][y] and graph[y][x] equal to 1. The reason is this is an undirected graph so both 1 -> 2 and 2 -> 1 are valued edges.
2.The for loop to find the shortest path is not correct. You need to start at the dest and work you way back to the src. You can use the prev array to find you way from dst to src.

Below is the output from your program with the changes I detailed above, and its shortest path from 1 to 12.

$ ./a.out
Nodes, edges, source, destination? 12 12 1 12
Edge 1: 1 2
Edge 2: 1 3
Edge 3: 1 4
Edge 4: 2 6
Edge 5: 2 5
Edge 6: 5 10
Edge 7: 5 9
Edge 8: 3 7
Edge 9: 4 8
Edge 10: 4 7
Edge 11: 7 12
Edge 12: 7 11
1 2 3 4 5 6 7 8 9 10 11 12 
1 -> 3 -> 7 -> 12
$

[hawkeyeviewonu]

thanks for the replies, i changed the input part a little so it takes less time when testing..

still getting error, am i doing it wrong?

 #include <stdio.h>
 #include <queue>
 #include <conio.h>
 using namespace std;

 int nodes, edges, src, dest;
 int graph[100][100], color[100],distance[100],prev[100];
 const int WHITE = 0;
 const int GRAY = 1;
 const int BLACK = 2;

 int main() {
     printf("source and destination? ");
     printf("from 1 to 5 ");
     src=1; dest=5; nodes=5; edges=14;
     graph[1][2] = 1;
     graph[1][3] = 1;
     graph[2][1] = 1;
     graph[2][3] = 1;
     graph[2][4] = 1;
     graph[3][1] = 1;
     graph[3][2] = 1;
     graph[3][4] = 1;
     graph[3][5] = 1;
     graph[4][2] = 1;
     graph[4][3] = 1;
     graph[4][5] = 1;
     graph[5][3] = 1;
     graph[5][4] = 1;
     //run BFS
     queue<int> q;           //create a queue
     q.push(src);            //1. put root node on the queue
     do {
         int u = q.front();  //2. pull a node from the beginning of the queue
         q.pop();
         printf("%d ", u);   //print the node
         for (int i = 1; i <= nodes; i++) {  //4. get all the adjacent nodes
             if ((graph[u][i] == 1)  //if an edge exists between these two nodes,
                 && (color[i] == WHITE)) {   //and this adjacent node is still WHITE,
                 q.push(i);                  //4. push this node into the queue
                 color[i] = GRAY; prev[i] = u;            //color this adjacent node with GRAY
             }
         }
         color[u] = BLACK;   //color the current node black to mark it as dequeued
     } while (!q.empty());   //5. if the queue is empty, then all the nodes have been visited

         for(int i=dest;i=src; i--)
            {if (prev[i] == 0)
            {            }
            else
            printf("%d -> ", prev[i]); }
     getch();
     return 0;
 }

[histrungalot]

You need to walk backwards thru the prev array.
It looks like:

               src                     dst
              -----                   -----
          0     1     2     3     4     5     6     7
        --------------------------------------------------
prev = |  -  |  -  |  1  |  1  |  2  |  3  |  -  |  -  |  . . .
        --------------------------------------------------
                            ^           |
                            |           |
                             -----------

First check if src == dst, if true then done. Next at prev[5]. The value in there says that node 3 is the node that discovered node 5. So, now go to prev[3] to see who discovered it, node 1. Now, you have gone from the dst to the src.

The shortest path in reverse is: 5 <- 3 <- 1. Then you could reverse the list or build it in reverse.