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

[jinnejeevansai]

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.

#include <stdio.h>
#include <stdlib.h>

int count=0;

struct node{
    
    int value;
    struct node *next;
    struct node *prev;
};

struct node *root=NULL,*tra=NULL;

void bfs(int n,int a[][n],int start,int end,int value[]){
    
    for(int i=0;i<n ;i++){
        
        if(i==start)
        continue;
        
        if(a[start][i] == 1 ){
            
            
            if(value[i] == 0 || value[i] > value[start] + 1 ){
                
                value[i] = value[start] + 1;
                
                struct node *p;
                
                p = (struct node *)malloc(sizeof(struct node));
                p->value = i;
                p->next = root;
                p->prev = NULL;
                root->prev = p;
                
                root = p;
            }
        }
    }
    
    return;
}

int main()
{
    int t;
    scanf("%d",&t);
    
    for(int i=0;i<t;i++){
        
        int n;
        scanf("%d",&n);
        
        int a[n][n],start,end,value[n];
        struct node *temp;
        
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                scanf("%d",&a[j][k]);
            }
        }
        
        
        memset(value,0,n*4);
        scanf("%d %d",&start,&end);
        
        value[start]=1;
        
        temp = (struct node *)malloc(sizeof(struct node));
        temp->value = start;
        temp->next = NULL;
        temp->prev = NULL;
        
        root = temp;
        tra = temp;
        
        
        while(tra != NULL){
            
            bfs(n,a,tra->value,end,value);
            tra = tra->prev;
        }
        
        printf("%d\n",value[end]-1);
        
        int x = end;
        
        int p[n],pi=0;
        p[pi++] = x;
        
        while(1){
            
            for(int j=0;j<n;j++){
                if((value[j] == value[x]-1) &&(a[j][x] == 1)){
                    //	printf("%d ",j);
                    p[pi++] = j;
                    
                    x=j;
                    break;
                    
                }
            }
            if(x == start){
                break;
            }
            
        }
        
        for(int j=pi-1;j>=0;j--){
            printf("%d ",p[j]);
            
        }
    }
    return 0;
}