編集履歴

質問編集履歴

自己解決

2019/10/19 07:14

投稿

スコア8

test CHANGED Viewed

	@@ -1 +1 @@
1	- c言語　~~ダイクストラ法~~
1	+ c言語　自己解決済み

test CHANGED Viewed

@@ -1,219 +1,5 @@
-c言語でダイクストラ法を実装してます。
+c言語　ダイクストラ法
-コンパイル後実行して、始点終点を入力した後に固まってしまいます。
+自己解決済みです。
-/////////////////
-```
-#include <stdio.h>
-#include <stdlib.h>
-#include <time.h>
-#define NODE_NUM 10 /* 総ノード数 */
-#define MAX 9999 /* 無限大に相当する数 */
-#define TRUE 1
+繰返し部分が誤っておりました
-#define FALSE 0
-int main()
-{
-/* Dijkstraのアルゴリズム部分で必要な変数 */
-  int graph[NODE_NUM][NODE_NUM]; /* 距離行列 */
-  int path[NODE_NUM]; /* 前ノード表 */
-  int dist[NODE_NUM]; /* 距離を格納 */
-  int chk[NODE_NUM]; /* 最短距離確定のフラグ */
-  int tmp_node, tmp_dist; /* 注目しているノードとそこまでの最短距離 */
-  int src, dest; /* 始点・終点ノード */
-  int a, b, c, d, i, j;
-  int fin; /* 未確定ノードが残っているかどうかのフラグ */
-  FILE *fp; /* 距離の入ったファイルを示すポインタ */
-/*
-距離行列の作成
-*/
-  for(i=0; i<NODE_NUM; i++){
-    for(j=0; j<NODE_NUM; j++){
-      graph[i][j] = MAX; /* 接続されていないノード間の距離をMAXにする */
-      if(i==j){graph[i][j] = 0;}
-    }
-  }
-  fp=fopen("./distance.txt", "r");
-  while(fscanf(fp, "%d %d %d %d", &a, &b, &c, &d) != EOF) /* EOFまで4つ組を読み込む */
-    {
-      graph[a][b]=c;
-      graph[b][a]=c;
-    }
-  fclose(fp);
-    printf("Source Node?(0-%d)", NODE_NUM-1);
-    fscanf(stdin, "%d", &src);
-    printf("Destination Node?(0-%d)", NODE_NUM-1);
-    fscanf(stdin, "%d", &dest);
-for(i=0; i<NODE_NUM; i++){
-        dist[i] = MAX;
-        chk[i] = 0;
-        path[i] = NODE_NUM;
-      }
-      path[src] = src;
-      dist[src] = 0;
-      chk[src] = 1;
-      tmp_node = src;
-      fin = 0;
-        int min = MAX;
-        int target;
-    while(fin == 0){
-        for(i=0; i<NODE_NUM; i++){
-          if(!chk[i] && dist[i]<min){
-             min = dist[i];
-             target = i ;
-          }
-        }
-         for(tmp_node=0 ; tmp_node<NODE_NUM ;tmp_node++){
-            if(dist[tmp_node] > graph[target][tmp_node] + dist[target]){
-                tmp_dist = graph[target][tmp_node] + dist[target];
-                path[tmp_node] = target;
-            }
-         }
-         chk[target] = TRUE ;
-　　　　if(chk[dest] == 1) fin = 1;
-        }
-if(dist[dest]>=MAX){
-          printf("No path from node%d to node%d.\n",src,dest);
-        }else{
-          printf("Shortest path from node%d to node%d is as follows.\n",src,dest);
-          printf("%d <- ",dest);
-          i=dest;
-          for(i=path[i]; i!=src; i=path[i]){/* 前ノード表を辿る */
-          }
-          printf("%d\n",src);
-          printf("Shortest distance is %d.\n", dist[dest]);
-        }
-        return 0;
-      }
-```

改善

2019/10/19 07:14

投稿

hheytakuc

スコア8

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -146,7 +146,7 @@
-        for(i; i<NODE_NUM; i++){
+        for(i=0; i<NODE_NUM; i++){

不要なところが入っていたので消しました。

2019/10/18 08:54

投稿

hheytakuc

スコア8

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -94,7 +94,7 @@
   fclose(fp);
-  if (FLAG == 0){
     printf("Source Node?(0-%d)", NODE_NUM-1);
@@ -104,7 +104,7 @@
     fscanf(stdin, "%d", &dest);
-  }
@@ -140,7 +140,7 @@
-        while(fin == 0){
+    while(fin == 0){

コードをすべて載せました。

2019/10/18 06:00

投稿

hheytakuc

スコア8

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -1,22 +1,110 @@
 c言語でダイクストラ法を実装してます。
-なかなかうまいこと動かないので、間違っているところがあれば教えてほしいです。
+コンパイル後実行して、始点終点を入力した後に固まってしまいます。
-dist[] 距離
-chk[]　確定済みかどうか
-path[]  通った道
-tmp_node 注目ノード
-tmp_node　確定距離
 /////////////////
+```
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#define NODE_NUM 10 /* 総ノード数 */
+#define MAX 9999 /* 無限大に相当する数 */
+#define TRUE 1
+#define FALSE 0
+int main()
+{
+/* Dijkstraのアルゴリズム部分で必要な変数 */
+  int graph[NODE_NUM][NODE_NUM]; /* 距離行列 */
+  int path[NODE_NUM]; /* 前ノード表 */
+  int dist[NODE_NUM]; /* 距離を格納 */
+  int chk[NODE_NUM]; /* 最短距離確定のフラグ */
+  int tmp_node, tmp_dist; /* 注目しているノードとそこまでの最短距離 */
+  int src, dest; /* 始点・終点ノード */
+  int a, b, c, d, i, j;
+  int fin; /* 未確定ノードが残っているかどうかのフラグ */
+  FILE *fp; /* 距離の入ったファイルを示すポインタ */
+/*
+距離行列の作成
+*/
+  for(i=0; i<NODE_NUM; i++){
+    for(j=0; j<NODE_NUM; j++){
+      graph[i][j] = MAX; /* 接続されていないノード間の距離をMAXにする */
+      if(i==j){graph[i][j] = 0;}
+    }
+  }
+  fp=fopen("./distance.txt", "r");
+  while(fscanf(fp, "%d %d %d %d", &a, &b, &c, &d) != EOF) /* EOFまで4つ組を読み込む */
+    {
+      graph[a][b]=c;
+      graph[b][a]=c;
+    }
+  fclose(fp);
+  if (FLAG == 0){
+    printf("Source Node?(0-%d)", NODE_NUM-1);
+    fscanf(stdin, "%d", &src);
+    printf("Destination Node?(0-%d)", NODE_NUM-1);
+    fscanf(stdin, "%d", &dest);
+  }
@@ -97,3 +185,35 @@
         }
+if(dist[dest]>=MAX){
+          printf("No path from node%d to node%d.\n",src,dest);
+        }else{
+          printf("Shortest path from node%d to node%d is as follows.\n",src,dest);
+          printf("%d <- ",dest);
+          i=dest;
+          for(i=path[i]; i!=src; i=path[i]){/* 前ノード表を辿る */
+          }
+          printf("%d\n",src);
+          printf("Shortest distance is %d.\n", dist[dest]);
+        }
+        return 0;
+      }
+```