By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,959 Members | 1,139 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,959 IT Pros & Developers. It's quick & easy.

how to find the path of shortest distance between two vertices in a graph using bfs

P: 48
It is also given that in case of a tie, a smaller indexed vertex should be preferable to a larger indexed vertex.


First in my approach i traversed graph using bfs finding distances of all vertices from start node ,i got the path length from start to end node,then i traversed from end node to start node by viewing if the length of node is one less than previous,but i am missing some point in between when i submit my code it is not correct for all test cases,please can someone find what is my mistake.


Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int count=0;
  5.  
  6. struct node{
  7.  
  8.     int value;
  9.     struct node *next;
  10.     struct node *prev;
  11. };
  12.  
  13. struct node *root=NULL,*tra=NULL;
  14.  
  15. void bfs(int n,int a[][n],int start,int end,int value[]){
  16.  
  17.     for(int i=0;i<n ;i++){
  18.  
  19.         if(i==start)
  20.         continue;
  21.  
  22.         if(a[start][i] == 1 ){
  23.  
  24.  
  25.             if(value[i] == 0 || value[i] > value[start] + 1 ){
  26.  
  27.                 value[i] = value[start] + 1;
  28.  
  29.                 struct node *p;
  30.  
  31.                 p = (struct node *)malloc(sizeof(struct node));
  32.                 p->value = i;
  33.                 p->next = root;
  34.                 p->prev = NULL;
  35.                 root->prev = p;
  36.  
  37.                 root = p;
  38.             }
  39.         }
  40.     }
  41.  
  42.     return;
  43. }
  44.  
  45. int main()
  46. {
  47.     int t;
  48.     scanf("%d",&t);
  49.  
  50.     for(int i=0;i<t;i++){
  51.  
  52.         int n;
  53.         scanf("%d",&n);
  54.  
  55.         int a[n][n],start,end,value[n];
  56.         struct node *temp;
  57.  
  58.         for(int j=0;j<n;j++){
  59.             for(int k=0;k<n;k++){
  60.                 scanf("%d",&a[j][k]);
  61.             }
  62.         }
  63.  
  64.  
  65.         memset(value,0,n*4);
  66.         scanf("%d %d",&start,&end);
  67.  
  68.         value[start]=1;
  69.  
  70.         temp = (struct node *)malloc(sizeof(struct node));
  71.         temp->value = start;
  72.         temp->next = NULL;
  73.         temp->prev = NULL;
  74.  
  75.         root = temp;
  76.         tra = temp;
  77.  
  78.  
  79.         while(tra != NULL){
  80.  
  81.             bfs(n,a,tra->value,end,value);
  82.             tra = tra->prev;
  83.         }
  84.  
  85.         printf("%d\n",value[end]-1);
  86.  
  87.         int x = end;
  88.  
  89.         int p[n],pi=0;
  90.         p[pi++] = x;
  91.  
  92.         while(1){
  93.  
  94.             for(int j=0;j<n;j++){
  95.                 if((value[j] == value[x]-1) &&(a[j][x] == 1)){
  96.                     //    printf("%d ",j);
  97.                     p[pi++] = j;
  98.  
  99.                     x=j;
  100.                     break;
  101.  
  102.                 }
  103.             }
  104.             if(x == start){
  105.                 break;
  106.             }
  107.  
  108.         }
  109.  
  110.         for(int j=pi-1;j>=0;j--){
  111.             printf("%d ",p[j]);
  112.  
  113.         }
  114.     }
  115.     return 0;
  116. }
  117.  
Aug 17 '16 #1
Share this question for a faster answer!
Share on Google+

Post your reply

Sign in to post your reply or Sign up for a free account.