最小距离使用深度优先搜索 (DFS)

huangapple
go评论99阅读模式
英文:

minimum distance using dfs

问题

  1. // 修改
  2. void dfs(int current_node_index, int end_node_index, int num_nodes, int graph[][num_nodes], Node nodes[]) {
  3.     nodes[current_node_index].visited = 1;
  4.     if (current_node_index == end_node_index) {
  5.         return;
  6.     }
  7.     for (int i = 0; i < num_nodes; i++) {
  8.         if (graph[current_node_index][i] != INFINITY && !nodes[i].visited) {
  9.             int new_distance = nodes[current_node_index].distance + graph[current_node_index][i];
  10.             if (new_distance < nodes[i].distance) {
  11.                 nodes[i].distance = new_distance;
  12.             }
  13.             dfs(i, end_node_index, num_nodes, graph, nodes);
  14.         }
  15.     }
  16. }
  18. // 修改
  19. for (int i = 0; i < 3; i++) {
  20.     fgets(line, MAX_LENGTH, input_file);
  21.     sscanf(line, "%s %s", start_node, end_node);
  22.     // Initialize graph and nodes
  23.     int graph[num_nodes][num_nodes];
  24.     char nodes[num_nodes][MAX_LENGTH];
  25.     for (int i = 0; i < num_nodes; i++) {
  26.         for (int j = 0; j < num_nodes; j++) {
  27.             graph[i][j] = INFINITY;
  28.         }
  29.         strcpy(nodes[i], "");
  30.     }
  32.     // Populate graph and nodes with edges
  33.     for (int i = 0; i < num_edges; i++) {
  34.         int source_index = get_node_index(edges[i].source, nodes, num_nodes);
  35.         if (source_index == -1) {
  36.             strcpy(nodes[num_nodes], edges[i].source);
  37.             source_index = num_nodes;
  38.             num_nodes++;
  39.         }
  40.         int destination_index = get_node_index(edges[i].destination, nodes, num_nodes);
  41.         if (destination_index == -1) {
  42.             strcpy(nodes[num_nodes], edges[i].destination);
  43.             destination_index = num_nodes;
  44.             num_nodes++;
  45.         }
  46.         graph[source_index][destination_index] = edges[i].weight;
  47.     }
  49.     // Query the paths and write results to output file
  50.     Node query_nodes[num_nodes];
  51.     int start_node_index = get_node_index(start_node, nodes, num_nodes);
  52.     int end_node_index = get_node_index(end_node, nodes, num_nodes);
  54.     // Initialize nodes
  55.     for (int j = 0; j < num_nodes; j++) {
  56.         query_nodes[j].visited = 0;
  57.         query_nodes[j].distance = INFINITY;
  58.     }
  59.     query_nodes[start_node_index].distance = 0;
  61.     // Traverse graph with dfs
  62.     dfs(start_node_index, end_node_index, num_nodes, graph, query_nodes);
  64.     // Write result to output file
  65.     if (query_nodes[end_node_index].distance == INFINITY) {
  66.         fprintf(output_file, "NO PATH\n");
  67.     } else {
  68.         fprintf(output_file, "%d\n", query_nodes[end_node_index].distance);
  69.     }
  70. }
英文: 
  1. #include &lt;stdio.h&gt;
  2. #include &lt;stdlib.h&gt;
  3. #include &lt;string.h&gt;
  4. #define MAX_LENGTH 100
  5. #define INFINITY 99999
  6. typedef struct {
  7. char source[MAX_LENGTH];
  8. char destination[MAX_LENGTH];
  9. int weight;
  10. } Edge;
  11. typedef struct {
  12. int visited;
  13. int distance;
  14. } Node;
  15. int get_node_index(char* node_name, char nodes[][MAX_LENGTH], int num_nodes) {
  16. for (int i = 0; i &lt; num_nodes; i++) {
  17. if (strcmp(node_name, nodes[i]) == 0) {
  18. return i;
  19. }
  20. }
  21. return -1;
  22. }
  23. void dfs(int current_node_index, int end_node_index, int num_nodes, int graph[][num_nodes], Node nodes[]) {
  24. nodes[current_node_index].visited = 1;
  25. if (current_node_index == end_node_index) {
  26. return;
  27. }
  28. for (int i = 0; i &lt; num_nodes; i++) {
  29. if (graph[current_node_index][i] != INFINITY &amp;&amp; !nodes[i].visited) {
  30. int new_distance = nodes[current_node_index].distance + graph[current_node_index][i];
  31. if (new_distance &lt; nodes[i].distance) {
  32. nodes[i].distance = new_distance;
  33. }
  34. dfs(i, end_node_index, num_nodes, graph, nodes);
  35. }
  36. }
  37. }
  38. int main(int argc, char *argv[]) {
  39. if (argc != 5 || strcmp(argv[1], &quot;-i&quot;) != 0 || strcmp(argv[3], &quot;-o&quot;) != 0) {
  40. printf(&quot;Usage: %s -i &lt;input_file&gt; -o &lt;output_file&gt;\n&quot;, argv[0]);
  41. return 1;
  42. }
  43. // Open input file
  44. FILE *input_file = fopen(argv[2], &quot;r&quot;);
  45. if (input_file == NULL) {
  46. printf(&quot;Error: Cannot open input file\n&quot;);
  47. return 1;
  48. }
  49. // Open output file
  50. FILE *output_file = fopen(argv[4], &quot;w&quot;);
  51. if (output_file == NULL) {
  52. printf(&quot;Error: Cannot open output file\n&quot;);
  53. fclose(input_file);
  54. return 1;
  55. }
  56. int num_nodes, num_edges;
  57. char line[MAX_LENGTH];
  58. Edge edges[MAX_LENGTH];
  59. // Read the first line to get the number of nodes and edges
  60. fgets(line, MAX_LENGTH, input_file);
  61. sscanf(line, &quot;%d %d&quot;, &amp;num_nodes, &amp;num_edges);
  62. // Read the rest of the lines to get the edges
  63. for (int i = 0; i &lt; num_edges; i++) {
  64. fgets(line, MAX_LENGTH, input_file);
  65. sscanf(line, &quot;%s %s %d&quot;, edges[i].source, edges[i].destination, &amp;edges[i].weight);
  66. }
  67. // Write the directed weighted graph to the output file
  68. for (int i = 0; i &lt; num_edges; i++) {
  69. fprintf(output_file, &quot;%s -&gt; %s %d\n&quot;, edges[i].source, edges[i].destination, edges[i].weight);
  70. }
  71. // Read the last three lines to get the paths to query
  72. char start_node[MAX_LENGTH], end_node[MAX_LENGTH];
  73. int distance;
  74. for (int i = 0; i &lt; 3; i++) {
  75. fgets(line, MAX_LENGTH, input_file);
  76. sscanf(line, &quot;%s %s&quot;, start_node, end_node);
  77. }
  78. // Initialize graph and nodes
  79. int graph[num_nodes][num_nodes];
  80. char nodes[num_nodes][MAX_LENGTH];
  81. for (int i = 0; i &lt; num_nodes; i++) {
  82. for (int j = 0; j &lt; num_nodes; j++) {
  83. graph[i][j] = INFINITY;
  84. }
  85. strcpy(nodes[i], &quot;&quot;);
  86. }
  87. // Populate graph and nodes with edges
  88. for (int i = 0; i &lt; num_edges; i++) {
  89. int source_index = get_node_index(edges[i].source, nodes, num_nodes);
  90. if (source_index == -1) {
  91. strcpy(nodes[num_nodes], edges[i].source);
  92. source_index = num_nodes;
  93. num_nodes++;
  94. }
  95. int destination_index = get_node_index(edges[i].destination, nodes, num_nodes);
  96. if (destination_index == -1) {
  97. strcpy(nodes[num_nodes], edges[i].destination);
  98. destination_index = num_nodes;
  99. num_nodes++;
  100. }
  101. graph[source_index][destination_index] = edges[i].weight;
  102. }
  103. // Query the paths and write results to output file
  104. Node query_nodes[num_nodes];
  105. for (int i = 0; i &lt; 3; i++) {
  106. int start_node_index = get_node_index(start_node, nodes, num_nodes);
  107. int end_node_index = get_node_index(end_node, nodes, num_nodes);
  108. // Initialize nodes
  109. for (int j = 0; j &lt; num_nodes; j++) {
  110. query_nodes[j].visited = 0;
  111. query_nodes[j].distance = INFINITY;
  112. }
  113. query_nodes[start_node_index].distance = 0;
  114. // Traverse graph with dfs
  115. dfs(start_node_index, end_node_index, num_nodes, graph, query_nodes);
  116. // Write result to output file
  117. if (query_nodes[end_node_index].distance == INFINITY) {
  118. fprintf(output_file, &quot;NO PATH\n&quot;);
  119. } else {
  120. fprintf(output_file, &quot;%d\n&quot;, query_nodes[end_node_index].distance);
  121. }
  122. }
  123. // Close the input and output files
  124. fclose(input_file);
  125. fclose(output_file);
  126. return 0;
  127. }

i have a weighted directed graph which is implemented by the following input file:

  1. 7 11
  2. Prague Helsinki 1845
  3. Prague London 1264
  4. Beijing London 8132
  5. Beijing Tokyo 1303
  6. Beijing NewYork 11550
  7. Helsinki Tokyo 7815
  8. Tokyo Jakarta 5782
  9. Tokyo NewYork 10838
  10. Jakarta Beijing 4616
  11. NewYork London 5567
  12. London Tokyo 9566
  13. Prague London
  14. London London
  15. 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:

  1. Prague -&gt; Helsinki 1845
  2. Prague -&gt; London 1264
  3. Beijing -&gt; London 8132
  4. Beijing -&gt; Tokyo 1303
  5. Beijing -&gt; NewYork 11550
  6. Helsinki -&gt; Tokyo 7815
  7. Tokyo -&gt; Jakarta 5782
  8. Tokyo -&gt; NewYork 10838
  9. Jakarta -&gt; Beijing 4616
  10. NewYork -&gt; London 5567
  11. London -&gt; Tokyo 9566
  12. NO PATH
  13. NO PATH
  14. NO PATH

but the output should be as follows:

  1. Path (Prague London) : Prague -&gt; Helsinki -&gt; Tokyo -&gt; New York -&gt; London
  2. Distance: 26065 km
  3. Path (London London): London -&gt; Tokyo -&gt; New York -&gt; London
  4. Distance: 25971 km
  5. Path (London Prague): Path not found
  6. Distance: Path not found

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

答案1

得分: 1

当您的程序使用 gcc -fsanitize=address ... 构建时，它会产生以下诊断信息：

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

这个代码片段：

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

可以_保证_会破坏堆栈。

看起来您需要一个_单独的_变量来存储 num_nodes，也许可以使用 nodes_so_far，您可以从0开始使用它来填充节点。

英文:

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

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

This sequence:

  1.     char nodes[num_nodes][MAX_LENGTH];
  2. ...
  3. 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?

huangapple
  • 本文由 发表于 2023年5月15日 04:00:15
  • 转载请务必保留本文链接：https://go.coder-hub.com/76249441.html
  • c
  • data-structures
  • depth-first-search
  • graph-theory
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定