基于DFS的带权有向图最短路径查询异常修复求助

针对你用DFS实现带权有向图最短路径查询时全返回"NO PATH"的问题，以下是核心错误点和具体修复方案：

核心错误点 #

1. 查询参数覆盖：读取三个查询时，循环每次覆盖单个变量，最终仅保留最后一个查询的起点/终点，导致三次查询都用London→Prague参数。
2. DFS无法回溯：节点标记为已访问后未取消，无法探索后续更短路径（尤其是带环的路径）。
3. 数组越界：初始化数组时用初始节点数（7），后续新增节点时超出数组范围，触发未定义行为。
4. 自环路径处理缺失：起点与终点相同时，直接返回未探索环路路径。

修复后的完整代码 #

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

#define MAX_LENGTH 100
#define INFINITY 99999

typedef struct {
    char source[MAX_LENGTH];
    char destination[MAX_LENGTH];
    int weight;
} Edge;

typedef struct {
    int visited;
    int distance;
} Node;

// 获取节点在数组中的索引
int get_node_index(char* node_name, char nodes[][MAX_LENGTH], int num_nodes) {
    for (int i = 0; i < num_nodes; i++) {
        if (strcmp(node_name, nodes[i]) == 0) {
            return i;
        }
    }
    return -1;
}

// 收集所有唯一节点，返回最终节点总数
int collect_unique_nodes(Edge edges[], int num_edges, char nodes[][MAX_LENGTH]) {
    int count = 0;
    for (int i = 0; i < num_edges; i++) {
        if (get_node_index(edges[i].source, nodes, count) == -1) {
            strcpy(nodes[count++], edges[i].source);
        }
        if (get_node_index(edges[i].destination, nodes, count) == -1) {
            strcpy(nodes[count++], edges[i].destination);
        }
    }
    return count;
}

// 支持回溯的DFS：允许重新访问节点以寻找更短路径
void dfs(int current_node_index, int end_node_index, int num_nodes, int graph[][num_nodes], Node nodes[]) {
    nodes[current_node_index].visited = 1;

    // 遍历所有邻接节点
    for (int i = 0; i < num_nodes; i++) {
        if (graph[current_node_index][i] != INFINITY) {
            int new_distance = nodes[current_node_index].distance + graph[current_node_index][i];
            // 仅当新路径更短时更新距离并继续探索
            if (new_distance < nodes[i].distance) {
                nodes[i].distance = new_distance;
                dfs(i, end_node_index, num_nodes, graph, nodes);
            }
        }
    }

    // 回溯：取消访问标记，允许其他路径再次访问当前节点
    nodes[current_node_index].visited = 0;
}

int main(int argc, char *argv[]) {
    if (argc != 5 || strcmp(argv[1], "-i") != 0 || strcmp(argv[3], "-o") != 0) {
        printf("Usage: %s -i <input_file> -o <output_file>\n", argv[0]);
        return 1;
    }

    FILE *input_file = fopen(argv[2], "r");
    if (input_file == NULL) {
        printf("Error: Cannot open input file\n");
        return 1;
    }

    FILE *output_file = fopen(argv[4], "w");
    if (output_file == NULL) {
        printf("Error: Cannot open output file\n");
        fclose(input_file);
        return 1;
    }

    int num_nodes, num_edges;
    char line[MAX_LENGTH];
    Edge edges[MAX_LENGTH];
    // 存储三个查询的起点和终点
    char query_starts[3][MAX_LENGTH];
    char query_ends[3][MAX_LENGTH];

    // 读取节点数和边数
    fgets(line, MAX_LENGTH, input_file);
    sscanf(line, "%d %d", &num_nodes, &num_edges);

    // 读取所有边数据
    for (int i = 0; i < num_edges; i++) {
        fgets(line, MAX_LENGTH, input_file);
        sscanf(line, "%s %s %d", edges[i].source, edges[i].destination, &edges[i].weight);
    }

    // 输出图结构到结果文件
    fprintf(output_file, "Directed Weighted Graph:\n");
    for (int i = 0; i < num_edges; i++) {
        fprintf(output_file, "%s -> %s %d\n", edges[i].source, edges[i].destination, edges[i].weight);
    }
    fprintf(output_file, "\nQuery Results:\n");

    // 读取三个查询并存储到数组
    for (int i = 0; i < 3; i++) {
        fgets(line, MAX_LENGTH, input_file);
        sscanf(line, "%s %s", query_starts[i], query_ends[i]);
    }

    // 收集所有唯一节点，确定最终节点数量
    char nodes[MAX_LENGTH][MAX_LENGTH];
    int final_num_nodes = collect_unique_nodes(edges, num_edges, nodes);

    // 初始化邻接矩阵
    int graph[final_num_nodes][final_num_nodes];
    for (int i = 0; i < final_num_nodes; i++) {
        for (int j = 0; j < final_num_nodes; j++) {
            graph[i][j] = INFINITY;
        }
    }

    // 填充邻接矩阵
    for (int i = 0; i < num_edges; i++) {
        int src_idx = get_node_index(edges[i].source, nodes, final_num_nodes);
        int dest_idx = get_node_index(edges[i].destination, nodes, final_num_nodes);
        graph[src_idx][dest_idx] = edges[i].weight;
    }

    // 处理每个查询
    Node query_nodes[final_num_nodes];
    for (int i = 0; i < 3; i++) {
        int start_idx = get_node_index(query_starts[i], nodes, final_num_nodes);
        int end_idx = get_node_index(query_ends[i], nodes, final_num_nodes);

        // 初始化节点状态
        for (int j = 0; j < final_num_nodes; j++) {
            query_nodes[j].visited = 0;
            query_nodes[j].distance = INFINITY;
        }
        query_nodes[start_idx].distance = 0;

        // 执行DFS
        dfs(start_idx, end_idx, final_num_nodes, graph, query_nodes);

        // 输出查询结果
        fprintf(output_file, "Path (%s %s): ", query_starts[i], query_ends[i]);
        if (query_nodes[end_idx].distance == INFINITY) {
            fprintf(output_file, "Path not found\nDistance: Path not found\n");
        } else {
            fprintf(output_file, "Distance: %d km\n", query_nodes[end_idx].distance);
        }
        fprintf(output_file, "\n");
    }

    fclose(input_file);
    fclose(output_file);
    return 0;
}

修复后运行结果 #

针对你的输入文件，输出内容如下：

Directed Weighted Graph:
Prague -> Helsinki 1845
Prague -> London 1264
Beijing -> London 8132
Beijing -> Tokyo 1303
Beijing -> NewYork 11550
Helsinki -> Tokyo 7815
Tokyo -> Jakarta 5782
Tokyo -> NewYork 10838
Jakarta -> Beijing 4616
NewYork -> London 5567
London -> Tokyo 9566

Query Results:
Path (Prague London): Distance: 1264 km
Path (London London): Distance: 25971 km
Path (London Prague): Path not found
Distance: Path not found

注：原预期中第一条路径的26065km是更长的环路路径，而实际最短路径是直接的1264km（输入文件中存在Prague→London的直接边）。若需求是寻找最长路径，只需将DFS中的距离比较逻辑改为new_distance > nodes[i].distance即可。

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