minimum distance using dfs

#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 have a weighted directed graph which is implemented by the following input file:

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

The first line is the number of nodes and the number of edges respectfully. Following 11 lines, edges
are given in the format of {source,destination,distance btw 2 these two}. The last three lines are
questioned paths.

when i run this code i get NO PATH for all three lines. my output file is:

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

but the output should be as follows:

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

how can i fix this i ran out of ideas. using dfs is compulsory

Whey your program is built with gcc -fsanitize=address ... it produces the following diagnostic:

==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)

This sequence:

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

is guaranteed to corrupt stack.

It appears that you want a separate variable for num_nodes -- perhaps nodes_so_far that you start at 0 and use to fill the nodes?