C语言中邻接矩阵递归求图最短距离始终返回0问题求助

问题根源 #

1. min函数遍历长度错误 #

min函数循环条件用了i<numNodes，但传入的possNodes数组实际长度是当前节点的出边总数possPaths。当possPaths < numNodes时，会访问数组越界的内存区域，这些区域的随机值（比如0）会被当作最小值返回，直接导致最终结果为0。

2. 未回溯重置visited标记 #

递归调用时标记了visited[src] = 1，但递归返回后没有重置为0。这会锁死已访问节点，导致后续递归无法探索其他经过该节点的路径，同时可能遗漏更短路径。

3. 无出边节点的边界处理缺失 #

当当前节点没有出边时，possNodes数组长度为0，访问arr[0]会触发数组越界，引发未定义行为。

修复方案 #

1. 修正min函数的遍历长度 #

给min函数添加数组长度参数，避免越界访问：

int min(int arr[], int len){
    int minimum = arr[0], i;
    for(i=1 ; i<len ; i++){
       if(arr[i]<minimum){
          minimum = arr[i];
      }
   }
    return minimum;
}

调用时传入possPaths作为长度：return min(possNodes, possPaths);

2. 回溯重置visited状态 #

递归完成后重置当前节点的访问标记，允许后续路径重新访问：

int shortestDist(int src,int dst){
   // ... 原有代码 ...
   // 递归探索间接路径
   for(i=0;i<numNodes;i++){
      if(graph[src][i]!=X && visited[i]==0 && i!=dst){
         possNodes[count] = graph[src][i] + shortestDist(i,dst);
         count++;
      }
   }
   // 回溯：重置访问标记
   visited[src] = 0;
   // ... 原有代码 ...
}

3. 处理无出边的边界情况 #

在初始化数组前判断是否无出边，返回极大值表示不可达：

int shortestDist(int src,int dst){
   int possPaths=0,i;
   int count=0;
   visited[src] = 1;

   // 统计当前节点的出边数量
   for(i=0;i<numNodes;i++){
      if(graph[src][i]!=X){
         possPaths++;
      }
   }

   // 无出边，返回不可达
   if(possPaths == 0){
       visited[src] = 0;
       return X;
   }
   // ... 原有代码 ...
}

修改后的完整代码 #

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define X 99
int **graph;
int numNodes;
char nodes[10][10];
void createGraph(int);
void printGraph();
void addPath(char[],char[],int);
void deleteGraph();
int shortestDist(int,int);
int visited[10];
int min(int[], int);

int main()
{
   int i,j;
    createGraph(5);
    addPath("a","b",3);
    addPath("b","c",5);
    addPath("a","c",9);
    printf ("\n最短路径长度：%d\n",shortestDist(0,2));
    printGraph();
    deleteGraph();
    return 0;
}

void createGraph(int no){
   int i,j;
   numNodes=no;
    graph = malloc(sizeof(int*)*no);
    for(i=0;i<no;i++){
        graph[i] = malloc(sizeof(int)*no);
        visited[i] = 0;
    }
    for(i=0;i<no;i++){
       printf("Enter %d node: ",i+1);
       scanf("%s",nodes[i]);
        for(j=0;j<no;j++){
            graph[i][j] = X;
        }
    }
}

void addPath(char from[],char to[],int dist){
   int i,j;
   for(i=0;i<numNodes;i++){
      if(strcmp(from,nodes[i])==0){
          for(j=0;j<numNodes;j++){
              if(strcmp(to,nodes[j])==0){
                  graph[i][j] = dist;
                  break;
              }
          }
          break;
      }
   }
}

void printGraph(){
   int i,j;
   printf("\n邻接矩阵：\n");
   for(i=0;i<numNodes;i++){
        for(j=0;j<numNodes;j++){
            printf("%d ",graph[i][j]);
        }
        printf("\n");
    }
    printf("\n访问标记：");
    for(i=0;i<numNodes;i++){
       printf("%d ",visited[i]);
   }
   printf("\n");
}

void deleteGraph(){
   for(int i=0; i<numNodes; i++){
       free(graph[i]);
   }
   free(graph);
}

int shortestDist(int src,int dst){
   int possPaths=0,i;
   int count=0;
   visited[src] = 1;

   // 统计当前节点的出边数量
   for(i=0;i<numNodes;i++){
      if(graph[src][i]!=X){
         possPaths++;
      }
   }

   // 无出边，返回不可达
   if(possPaths == 0){
       visited[src] = 0;
       return X;
   }

   int possNodes[possPaths];
   // 初始化所有路径为极大值
   for(i=0;i<possPaths;i++){
      possNodes[i] = X;
   }

   // 添加直接路径
   if(graph[src][dst]!=X){
      possNodes[count] = graph[src][dst];
      count++;
   }

   // 递归探索间接路径
   for(i=0;i<numNodes;i++){
      if(graph[src][i]!=X && visited[i]==0 && i!=dst){
         possNodes[count] = graph[src][i] + shortestDist(i,dst);
         count++;
      }
   }

   // 回溯：重置访问标记
   visited[src] = 0;

   // 返回最小路径长度
   return min(possNodes, possPaths);
}

int min(int arr[], int len){
    int minimum = arr[0], i;
    for(i=1 ; i<len ; i++){
       if(arr[i]<minimum){
          minimum = arr[i];
      }
   }
    return minimum;
}

额外优化点 #

• 修正createGraph中scanf的参数，去掉多余的&
• 完善deleteGraph的内存释放逻辑，避免内存泄漏
• 优化addPath的循环逻辑，找到匹配节点后直接跳出循环
• 让main函数符合C标准，返回0值

内容的提问来源于stack exchange，提问作者Dhruvil S Shah