C语言实现Dijkstra算法路径错误问题求助

核心问题定位 #

你遇到的非法路径问题，大概率是以下两个原因之一：

• 邻接矩阵中非直接连通的节点权重未设为无穷大，导致算法误判存在直接路径
• 前驱节点数组维护错误，路径回溯时跳过了必须的中间节点

针对性修复步骤 #

1. 修正邻接矩阵初始化逻辑 #

确保非直接连通的节点对权重设为INT_MAX（C语言中表示无穷大），自身到自身设为0，直接连通的节点设为对应权重。比如测试用例中C到F没有直接边，那么graph[C_idx][F_idx]必须是INT_MAX，不能是0或其他有效值。

2. 正确维护前驱节点数组 #

在更新节点最短距离时，必须同步更新该节点的前驱节点。比如当通过E节点更新F的最短距离时，F的前驱要设为E，而不是C。修正后的距离更新逻辑如下：

if (!visited[v] && graph[u][v] != INT_MAX && dist[v] > dist[u] + graph[u][v]) {
    dist[v] = dist[u] + graph[u][v];
    prev[v] = u; // 这里的u是当前找到的最短路径节点，确保前驱指向正确的中间节点
}

3. 修复路径回溯逻辑 #

从终点开始，沿着前驱节点依次回溯到起点，避免跳过任何节点。可以用数组存储回溯路径，再反向输出得到正确顺序：

// 回溯路径示例
char path[MAX_NODES][MAX_NAME_LEN];
int path_len = 0;
int curr = end_idx;
while (curr != -1) {
    strcpy(path[path_len], nodes[curr]);
    path_len++;
    if (curr == start_idx) break;
    curr = prev[curr];
}
// 反向输出路径
for (int i = path_len - 1; i >= 0; i--) {
    printf("%s", path[i]);
    if (i > 0) printf("->");
}

修正后的完整C代码 #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_NODES 10
#define MAX_NAME_LEN 10

// 查找节点对应的数组索引
int find_node_index(char nodes[][MAX_NAME_LEN], int num_nodes, char *name) {
    for (int i = 0; i < num_nodes; i++) {
        if (strcmp(nodes[i], name) == 0) {
            return i;
        }
    }
    return -1;
}

void dijkstra(int graph[MAX_NODES][MAX_NODES], int num_nodes, int start_idx, int end_idx, char nodes[][MAX_NAME_LEN]) {
    int dist[MAX_NODES];
    int visited[MAX_NODES];
    int prev[MAX_NODES];

    // 初始化：距离设为起点到各节点的直接距离，前驱默认指向起点（可达的话）
    for (int i = 0; i < num_nodes; i++) {
        dist[i] = graph[start_idx][i];
        visited[i] = 0;
        prev[i] = (graph[start_idx][i] != INT_MAX && i != start_idx) ? start_idx : -1;
    }
    dist[start_idx] = 0;
    visited[start_idx] = 1;

    // 迭代处理所有节点
    for (int i = 1; i < num_nodes; i++) {
        // 找到未访问的最短距离节点
        int min_dist = INT_MAX;
        int u = -1;
        for (int j = 0; j < num_nodes; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }
        if (u == -1) break; // 无更多可达节点
        visited[u] = 1;

        // 更新邻接节点的距离和前驱
        for (int v = 0; v < num_nodes; v++) {
            if (!visited[v] && graph[u][v] != INT_MAX && dist[v] > dist[u] + graph[u][v]) {
                dist[v] = dist[u] + graph[u][v];
                prev[v] = u;
            }
        }
    }

    // 输出结果
    printf("最短路径：");
    if (dist[end_idx] == INT_MAX) {
        printf("无可达路径\n");
        return;
    }

    // 回溯路径并存储
    char path[MAX_NODES][MAX_NAME_LEN];
    int path_len = 0;
    int curr = end_idx;
    while (curr != -1) {
        strcpy(path[path_len], nodes[curr]);
        path_len++;
        if (curr == start_idx) break;
        curr = prev[curr];
    }

    // 反向输出得到正确路径顺序
    for (int i = path_len - 1; i >= 0; i--) {
        printf("%s", path[i]);
        if (i > 0) printf("->");
    }
    printf("\n最短距离：%d\n", dist[end_idx]);
}

int main() {
    int num_nodes;
    char nodes[MAX_NODES][MAX_NAME_LEN];
    int graph[MAX_NODES][MAX_NODES];
    char start_node[MAX_NAME_LEN], end_node[MAX_NAME_LEN];

    printf("输入节点数量：");
    scanf("%d", &num_nodes);
    getchar(); // 清除换行符

    printf("输入节点名称（每行一个）：\n");
    for (int i = 0; i < num_nodes; i++) {
        fgets(nodes[i], MAX_NAME_LEN, stdin);
        nodes[i][strcspn(nodes[i], "\n")] = '\0'; // 去掉末尾换行
    }

    // 初始化邻接矩阵为无穷大
    for (int i = 0; i < num_nodes; i++) {
        for (int j = 0; j < num_nodes; j++) {
            graph[i][j] = INT_MAX;
        }
        graph[i][i] = 0; // 自身到自身距离为0
    }

    printf("输入邻接矩阵（每行%d个数字，无穷大输入-1）：\n", num_nodes);
    for (int i = 0; i < num_nodes; i++) {
        for (int j = 0; j < num_nodes; j++) {
            int val;
            scanf("%d", &val);
            if (val != -1 && i != j) {
                graph[i][j] = val;
            }
        }
    }

    printf("输入起点和终点：");
    scanf("%s %s", start_node, end_node);

    int start_idx = find_node_index(nodes, num_nodes, start_node);
    int end_idx = find_node_index(nodes, num_nodes, end_node);

    if (start_idx == -1 || end_idx == -1) {
        printf("节点不存在\n");
        return 1;
    }

    dijkstra(graph, num_nodes, start_idx, end_idx, nodes);

    return 0;
}

测试用例验证 #

用你提到的测试场景输入：

节点数量：5
节点名称：
A
B
C
E
F
邻接矩阵：
0 -1 2 -1 -1
-1 0 -1 3 -1
-1 -1 0 1 -1
-1 -1 -1 0 1
-1 -1 -1 -1 0
起点：A，终点：F

运行后会输出正确路径：A->C->E->F，最短距离为4。

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