C语言 使用dfs的最小距离[闭合]

ca1c2owp  于 2023-05-16  发布在  其他
关注(0)|答案(1)|浏览(136)

**关闭。**此题需要debugging details。目前不接受答复。

编辑问题以包含desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem。这将帮助其他人回答这个问题。
昨天关门了。
Improve this question

#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;
}

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;
    if (current_node_index == end_node_index) {
        return;
    }
    for (int i = 0; i < num_nodes; i++) {
        if (graph[current_node_index][i] != INFINITY && !nodes[i].visited) {
            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);
        }
    }
}

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;
    }

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

    // Open output file
    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];

    // Read the first line to get the number of nodes and edges
    fgets(line, MAX_LENGTH, input_file);
    sscanf(line, "%d %d", &num_nodes, &num_edges);

    // Read the rest of the lines to get the 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);
    }

    // Write the directed weighted graph to the output file
    for (int i = 0; i < num_edges; i++) {
        fprintf(output_file, "%s -> %s %d\n", edges[i].source, edges[i].destination, edges[i].weight);
    }

    // Read the last three lines to get the paths to query
    char start_node[MAX_LENGTH], end_node[MAX_LENGTH];
    int distance;
    for (int i = 0; i < 3; i++) {
        fgets(line, MAX_LENGTH, input_file);
        sscanf(line, "%s %s", start_node, end_node);
    }
    // Initialize graph and nodes
    int graph[num_nodes][num_nodes];
    char nodes[num_nodes][MAX_LENGTH];
    for (int i = 0; i < num_nodes; i++) {
        for (int j = 0; j < num_nodes; j++) {
            graph[i][j] = INFINITY;
        }
        strcpy(nodes[i], "");
    }
    
    // Populate graph and nodes with edges
    for (int i = 0; i < num_edges; i++) {
        int source_index = get_node_index(edges[i].source, nodes, num_nodes);
        if (source_index == -1) {
            strcpy(nodes[num_nodes], edges[i].source);
            source_index = num_nodes;
            num_nodes++;
        }
        int destination_index = get_node_index(edges[i].destination, nodes, num_nodes);
        if (destination_index == -1) {
            strcpy(nodes[num_nodes], edges[i].destination);
            destination_index = num_nodes;
            num_nodes++;
        }
        graph[source_index][destination_index] = edges[i].weight;
    }
    
    // Query the paths and write results to output file
    Node query_nodes[num_nodes];
    for (int i = 0; i < 3; i++) {
        int start_node_index = get_node_index(start_node, nodes, num_nodes);
        int end_node_index = get_node_index(end_node, nodes, num_nodes);
    
        // Initialize nodes
        for (int j = 0; j < num_nodes; j++) {
            query_nodes[j].visited = 0;
            query_nodes[j].distance = INFINITY;
        }
        query_nodes[start_node_index].distance = 0;
    
        // Traverse graph with dfs
        dfs(start_node_index, end_node_index, num_nodes, graph, query_nodes);
    
        // Write result to output file
        if (query_nodes[end_node_index].distance == INFINITY) {
            fprintf(output_file, "NO PATH\n");
        } else {
            fprintf(output_file, "%d\n", query_nodes[end_node_index].distance);
        }
    }
// Close the input and output files
fclose(input_file);
fclose(output_file);

return 0;
}

i有一个加权有向图,它由以下输入文件实现:

7 11
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
Prague London
London London
London Prague

第一行分别是节点数和边数。在11行之后,边以{源,目的地,距离btw 2这两个}的格式给出。最后三行是可疑路径。
当我运行这段代码时,我得到了所有三行都没有PATH。我的输出文件是:

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
NO PATH
NO PATH
NO PATH

但输出应如下所示:

Path (Prague London) : Prague -> Helsinki -> Tokyo -> New York -> London
Distance: 26065 km
Path (London London): London -> Tokyo -> New York -> London
Distance: 25971 km
Path (London Prague): Path not found
Distance: Path not found

怎么解决这个问题呢。我没有办法了。必须使用dfs

m528fe3b

m528fe3b1#

如果你的程序是用gcc -fsanitize=address ...构建的,它会产生以下诊断:

==3046851==ERROR: AddressSanitizer: dynamic-stack-buffer-overflow on address 0x7ffd03bbeffc at pc 0x7f0c8c0602ca bp 0x7ffd03bbed00 sp 0x7ffd03bbe4b0
WRITE of size 7 at 0x7ffd03bbeffc thread T0
    #0 0x7f0c8c0602c9 in __interceptor_strcpy ../../../../src/libsanitizer/asan/asan_interceptors.cpp:425
    #1 0x55848a48215c in main /tmp/t.c:105
    #2 0x7f0c8be46189 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #3 0x7f0c8be46244 in __libc_start_main_impl ../csu/libc-start.c:381
    #4 0x55848a4811c0 in _start (/tmp/a.out+0x21c0)

该序列:

char nodes[num_nodes][MAX_LENGTH];
...
    strcpy(nodes[num_nodes], edges[i].destination);

是 * 保证 * 损坏堆栈。
看起来您需要为num_nodes提供一个 separate 变量--也许是从0开始并用于填充节点的nodes_so_far

相关问题