基于邻接矩阵和BFS求解源点到终点所有最短路径的C语言算法

核心实现逻辑 #

全最短路径求解不能直接靠普通BFS枚举所有路径，否则会因为冗余搜索导致复杂度过高，整体分三步实现：

• 第一步：计算源点S到所有节点的最短距离数组dist[]，作为后续剪枝的判断依据
  • 无权图直接用BFS层序遍历计算，时间复杂度最低
  • 带非负权图用Dijkstra算法计算即可
• 第二步：基于最短距离裁剪合法边
  对任意边u→v，只有满足dist[u] + 边u→v的权值 == dist[v]时，这条边才可能出现在S到其他点的最短路径上。不符合该条件的边直接排除，原图会被裁剪为一个有向无环图（DAG），图中所有S到E的路径就是全部最短路径，不存在冗余分支。
• 第三步：在裁剪后的DAG上回溯搜索所有路径
  从S出发做深度优先搜索，每一步仅走筛选出的合法边，走到终点E时记录当前路径即可，因为提前做了边裁剪，搜索过程不会走绕路的无效分支。

C语言核心实现代码 #

基础定义 #

#define MAX_NODE 100
#define INF 0x3f3f3f3f // 表示无边的标记值
int graph[MAX_NODE][MAX_NODE]; // 邻接矩阵存储图
int dist[MAX_NODE]; // 存储S到各节点的最短距离
int path[MAX_NODE]; // 回溯过程暂存当前路径
int path_len = 0; // 当前路径长度
int path_cnt = 0; // 统计最短路径总数

无权图BFS计算最短距离 #

void bfs_calc_dist(int start, int total_node) {
    int queue[MAX_NODE];
    int front = 0, rear = 0;
    // 初始化距离数组
    for (int i = 0; i < total_node; i++) {
        dist[i] = -1;
    }
    dist[start] = 0;
    queue[rear++] = start;
    while (front < rear) {
        int u = queue[front++];
        for (int v = 0; v < total_node; v++) {
            // 存在边且v未被访问过
            if (graph[u][v] != INF && dist[v] == -1) {
                dist[v] = dist[u] + 1;
                queue[rear++] = v;
            }
        }
    }
}

回溯搜索所有最短路径 #

void dfs_find_all_path(int current, int target, int total_node) {
    path[path_len++] = current;
    // 走到终点，输出/存储当前路径
    if (current == target) {
        path_cnt++;
        printf("第%d条最短路径：", path_cnt);
        for (int i = 0; i < path_len; i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
        path_len--;
        return;
    }
    // 仅遍历合法的最短路径边
    for (int next = 0; next < total_node; next++) {
        if (graph[current][next] != INF && dist[current] + graph[current][next] == dist[next]) {
            dfs_find_all_path(next, target, total_node);
        }
    }
    // 回溯
    path_len--;
}

注意事项 #

• 禁止直接在原图上无差别枚举所有路径再比对长度，节点数超过20时路径量会呈指数级增长，直接超时，提前用dist数组裁剪非法边是控制复杂度的核心
• 带权图需要把bfs_calc_dist替换为Dijkstra算法计算dist数组即可，后续回溯逻辑完全通用
• 邻接矩阵遍历邻接点时必须跳过值为INF的位置，避免将不存在的边纳入计算
• 如果需要持久化存储所有路径，在走到终点时将path数组的内容拷贝到提前申请的二维数组或链表结构中即可，不要直接存指针，避免回溯时路径内容被覆盖

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