C语言实现Dijkstra最短路径调用shortest_path函数崩溃报错

返回值3221225725是Windows平台下典型的栈溢出错误，你的代码同时存在内存访问非法、野指针等多个问题，具体修复方案如下：

修复点列表 #

• 1. 删除栈上分配的超大cost数组 #

  shortest_path函数里定义的int cost[MAX_NB][MAX_NB]大小为800080004B = 244MB，远大于默认1-8MB的栈空间，直接触发栈溢出。你已经有全局的amatrix存储邻接矩阵，不需要额外复制一份cost数组，直接用amatrix即可。

• 2. 修复顶点数组野指针问题 #

  load_vertices里的stops pArray[MAX_NB]是局部栈变量，函数返回后空间被回收，全局数组arr里保存的地址全部变成野指针，后续访问直接崩溃。需要把pArray改成全局数组，或者用malloc动态分配每个顶点的内存。

• 3. 修正shortest_path里的顶点数量 #

  函数里你错误把n赋值为MAX_NB，应该使用全局变量n（即实际加载的顶点数），不需要循环8000次，既浪费性能还容易访问越界。

• 4. 初始化pred数组和visited数组 #

  • 整个pred数组初始值要设为-1，你只初始化了pred[0]=-1，其余值是随机垃圾值，会导致printpath递归时出现越界或无限递归。
  • 每次调用shortest_path前要把全局visited数组全部清零，避免上次调用的结果影响本次计算。

• 5. 修正语法和逻辑小错误 #

  • main函数里load_edges("edges.csv")后面缺少分号，补全。
  • load_vertices和load_edges里的feof判断逻辑有问题，会多加载一条无效数据，改成读取失败就终止循环。

关键修改代码示例 #

修改后的shortest_path函数 #

void shortest_path(int origin, int end){
    int distance[MAX_NB];
    int pred[MAX_NB];
    int count,minD,nextn,i,j;
    // 初始化pred和visited
    memset(pred, -1, sizeof(pred));
    memset(visited, 0, sizeof(visited));
    // 用全局实际顶点数，不要用MAX_NB
    int node_count = n;

    for (i = 0; i < node_count; i++) {
        // 直接用amatrix，不要cost数组
        distance[i] = amatrix[origin][i] == 0 ? INFINITY : amatrix[origin][i];
    }
    distance[origin] = 0;
    visited[origin] = 1;
    count = 1;

    while (count < node_count - 1) {
        minD = INFINITY;
        nextn = -1;
        for (i = 0; i < node_count; i++){
            if ((distance[i] < minD) && (visited[i] != 1)) {
                minD = distance[i];
                nextn = i;
            }
        }
        // 没有可达节点直接退出
        if(nextn == -1) break;
        visited[nextn] = 1;
    
        for (i = 0; i < node_count; i++) {
            if (!visited[i] && amatrix[nextn][i] != 0) {
                if (minD + amatrix[nextn][i] < distance[i]) {
                    distance[i] = minD + amatrix[nextn][i];
                    pred[i] = nextn;
                }
            }
        }
        count++;
    }
    printpath(pred, end);
}

修改后的load_vertices顶点存储逻辑 #

// 把pArray改成全局数组，避免野指针
stops pArray[MAX_NB];        
int load_vertices(char *fname){
    FILE *f;
    struct stops p;
    f=fopen(fname,"r");
    if(!f) { 
        printf("unable to open file\n"); 
        return 0; 
    }
    // 跳过表头
    fetch_stops( f, &p );
    int ngames = 0;
    while(ngames < MAX_NB) {
        fetch_stops( f, &pArray[ngames]);
        if(feof(f)) break;
        arr[ngames]=&pArray[ngames];
        ngames++;
    }
    printf("loaded %d vertices\n",ngames);
    fclose(f);
    graph = create_graph(ngames);
    return 1;
}

内容的提问来源于stack exchange，提问作者Kartik Mann