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