I have written the program to find shortest path using BSF algorithm in C.
Below is the code:

我已经用C语言编写了使用BSF算法查找最短路径的程序。以下是代码：

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

#define max 1000
int dist = 0;
int node, edge, INDEX, i, j;
    
struct queue {
    int *arr;
    int rear, front;
};

struct queue *createQueue() {
    struct queue *q = (struct queue *)malloc(sizeof(struct queue));
    q->front = q->rear = -1;
    q->arr = (int *)malloc(max * sizeof(int));
    return q;
}

bool isEmpty(struct queue *q) {
    return (q->front == -1);
}

int pop(struct queue *q) {
    int item;
    if (isEmpty(q)) {
        //printf("Queue is empty");
        item = -1;
    } else {
        item = q->arr[q->front];
        q->front++;
        if (q->front > q->rear) {
            //printf("Resetting queue ");
            q->front = q->rear = -1;
        }
    }
    return item;
}

void push(struct queue *q, int add_item) {
    if (q->rear == max - 1)
        printf("queue Overflow \n");
    else {
        if (isEmpty(q))
            q->front = 0;
        q->rear = q->rear + 1;
        q->arr[q->rear] = add_item;
    }
}

struct node {
    int vertex;
    struct node *next;
}; 

struct node *createNode(int vertex){
    struct node *newNode = (struct node* )malloc(sizeof(struct node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}

struct graph {
    int vertices;
    struct node **adjList;
    bool *visited;
    int *dist;
};

struct graph *createGraph(int vertices) {
    int i;
    struct graph *g = (struct graph *)malloc(sizeof(struct graph));
    g->vertices = vertices;
    g->adjList = (struct node **)malloc(vertices * sizeof(struct node *));
    g->visited = (bool *)malloc(vertices * sizeof(bool)); // Allocate memory for all vertices
    g->dist = (int *)malloc(vertices * sizeof(int));
    for (i = 0; i < vertices; i++) {
        g->adjList[i] = NULL;
        g->visited[i] = 0; // Initialize all vertices as not visited
        g->dist[i] = -1;
    }
    return g;
}

void addEdge(struct graph *g, int src, int dest) {
    struct node *newNode = createNode(dest);
    newNode->next = g->adjList[src];
    g->adjList[src] = newNode;
    
    newNode = createNode(src);
    newNode->next = g->adjList[dest];
    g->adjList[dest] = newNode;
}

void printQueue(struct queue *q) {
    int i;
    if (isEmpty(q)) {
        //printf("Queue is empty");
    } else {
        printf("\nQueue contains \n");
        for (i = q->front; i < q->rear + 1; i++) {
            printf("%d ", q->arr[i]);
        }
        printf("\n");
    }
}

int bfs(struct graph *g, int startVertex){
    struct queue *q = createQueue();
    
    g->visited[startVertex] = 1;
    push(q, startVertex);
    g->dist[startVertex] = 0;
    
    while (!isEmpty(q)) {
        printQueue(q);
        int currentVertex = pop(q);
        if (currentVertex == INDEX) {
            return g->dist[currentVertex];
        }
        printf("currentVertex = %d \n", currentVertex);
        struct node *temp = g->adjList[currentVertex];
        while (temp) {
            int adjNode = temp->vertex;
            if (!g->visited[adjNode]) {
                g->visited[adjNode] = 1;
                g->dist[adjNode] = g->dist[currentVertex] + 1;
                push(q, adjNode);
            }
            temp = temp->next;
        }
    }
    return -1;
}

int main() {
    scanf("%d %d %d", &node, &edge, &INDEX);
    struct graph *g = createGraph(node);
    
    for (i = 0; i < edge; i++) {
        int src, dest;
        scanf("%d %d", &src, &dest);
        addEdge(g, src, dest);
    }
    
    printf("shortest distance = %d", bfs(g, 4));
    
    return 0;
}

the code works fine if the starting node is 1 and 2 but when the starting node is 3, 4 or 5, the operation will be terminated and the main function will return 3221225477.
The output looks like this when the starting node is 3:

如果开始节点是1和2，则代码运行良好，但当开始节点是3、4或5时，操作将终止，Main函数将返回3221225477。当起始节点为3时，输出如下所示：

5 7 2
1 2
2 1
2 2
3 2
2 5
5 3
4 5
currentVertex = 3
currentVertex = 5

--------------------------------
Process exited after 9.651 seconds with return value 3221225477
Press any key to continue . . .

I am not sure what is wrong with the code, suggestions from chatgpt is not helping. I know C is probably not a good language to solve this problem but this is just for learning purposes, I hope can find an answer here or I'll have to give up using C for this.

我不确定代码出了什么问题，Chatgpt的建议无济于事。我知道C可能不是解决这个问题的好语言，但这只是为了学习目的，我希望能在这里找到答案，否则我将不得不放弃使用C来解决这个问题。

The problem is that you have not allocated entries in your graph structure for vertex 5 (in the example). The deeper cause is that the input specifies nodes by numbers between 1 to 𝑛, not between 0 and 𝑛−1. That means your algorithm will assign values to g->adjList[5], g->visited[5], g->dist[5] which are all outside of the allocated memory.

问题是您尚未在图结构中为顶点5分配条目(在本例中)。更深层次的原因是，输入指定的节点是介于1到𝑛之间的数字，而不是介于0和𝑛−1之间的数字。这意味着您的算法将为g->adjList[5]、g->Visted[5]、g->dist[5]赋值，这些值都在分配的内存之外。

The quick solution is to change the argument passed to createGraph:

快速解决方案是更改传递给createGraph的参数：

    struct graph* g = createGraph(node+1);

Unrelated to your question, but the input seems to suggest that the graph is directed (cf. 1→2 and 2→1 are both in the example input), while your code (at addEdge) treats it as undirected. You may want to review that choice.

与您的问题无关，但输入似乎表明该图是有向的(参见1→2和2→1都在示例输入中)，而您的代码(在addEdge)将其视为无定向。您可能想重新审视一下这一选择。