質問編集履歴
4
自己解決
title
CHANGED
|
@@ -1,1 +1,1 @@
|
|
|
1
|
-
c言語
|
|
1
|
+
c言語 自己解決済み
|
body
CHANGED
|
@@ -1,110 +1,3 @@
|
|
|
1
|
-
c言語
|
|
1
|
+
c言語 ダイクストラ法
|
|
2
|
-
コンパイル後実行して、始点終点を入力した後に固まってしまいます。
|
|
3
|
-
|
|
4
|
-
/////////////////
|
|
5
|
-
```
|
|
6
|
-
#include <stdio.h>
|
|
7
|
-
#include <stdlib.h>
|
|
8
|
-
|
|
2
|
+
自己解決済みです。
|
|
9
|
-
|
|
10
|
-
#define NODE_NUM 10 /* 総ノード数 */
|
|
11
|
-
#define MAX 9999 /* 無限大に相当する数 */
|
|
12
|
-
|
|
3
|
+
繰返し部分が誤っておりました
|
|
13
|
-
#define FALSE 0
|
|
14
|
-
|
|
15
|
-
|
|
16
|
-
int main()
|
|
17
|
-
{
|
|
18
|
-
/* Dijkstraのアルゴリズム部分で必要な変数 */
|
|
19
|
-
int graph[NODE_NUM][NODE_NUM]; /* 距離行列 */
|
|
20
|
-
int path[NODE_NUM]; /* 前ノード表 */
|
|
21
|
-
int dist[NODE_NUM]; /* 距離を格納 */
|
|
22
|
-
int chk[NODE_NUM]; /* 最短距離確定のフラグ */
|
|
23
|
-
int tmp_node, tmp_dist; /* 注目しているノードとそこまでの最短距離 */
|
|
24
|
-
int src, dest; /* 始点・終点ノード */
|
|
25
|
-
int a, b, c, d, i, j;
|
|
26
|
-
int fin; /* 未確定ノードが残っているかどうかのフラグ */
|
|
27
|
-
FILE *fp; /* 距離の入ったファイルを示すポインタ */
|
|
28
|
-
|
|
29
|
-
|
|
30
|
-
|
|
31
|
-
|
|
32
|
-
|
|
33
|
-
/*
|
|
34
|
-
距離行列の作成
|
|
35
|
-
*/
|
|
36
|
-
for(i=0; i<NODE_NUM; i++){
|
|
37
|
-
for(j=0; j<NODE_NUM; j++){
|
|
38
|
-
graph[i][j] = MAX; /* 接続されていないノード間の距離をMAXにする */
|
|
39
|
-
if(i==j){graph[i][j] = 0;}
|
|
40
|
-
}
|
|
41
|
-
}
|
|
42
|
-
fp=fopen("./distance.txt", "r");
|
|
43
|
-
while(fscanf(fp, "%d %d %d %d", &a, &b, &c, &d) != EOF) /* EOFまで4つ組を読み込む */
|
|
44
|
-
{
|
|
45
|
-
graph[a][b]=c;
|
|
46
|
-
graph[b][a]=c;
|
|
47
|
-
}
|
|
48
|
-
fclose(fp);
|
|
49
|
-
|
|
50
|
-
printf("Source Node?(0-%d)", NODE_NUM-1);
|
|
51
|
-
fscanf(stdin, "%d", &src);
|
|
52
|
-
printf("Destination Node?(0-%d)", NODE_NUM-1);
|
|
53
|
-
fscanf(stdin, "%d", &dest);
|
|
54
|
-
|
|
55
|
-
|
|
56
|
-
for(i=0; i<NODE_NUM; i++){
|
|
57
|
-
dist[i] = MAX;
|
|
58
|
-
chk[i] = 0;
|
|
59
|
-
path[i] = NODE_NUM;
|
|
60
|
-
}
|
|
61
|
-
path[src] = src;
|
|
62
|
-
dist[src] = 0;
|
|
63
|
-
chk[src] = 1;
|
|
64
|
-
tmp_node = src;
|
|
65
|
-
fin = 0;
|
|
66
|
-
|
|
67
|
-
|
|
68
|
-
|
|
69
|
-
int min = MAX;
|
|
70
|
-
int target;
|
|
71
|
-
|
|
72
|
-
while(fin == 0){
|
|
73
|
-
|
|
74
|
-
|
|
75
|
-
for(i=0; i<NODE_NUM; i++){
|
|
76
|
-
|
|
77
|
-
if(!chk[i] && dist[i]<min){
|
|
78
|
-
min = dist[i];
|
|
79
|
-
target = i ;
|
|
80
|
-
}
|
|
81
|
-
}
|
|
82
|
-
|
|
83
|
-
for(tmp_node=0 ; tmp_node<NODE_NUM ;tmp_node++){
|
|
84
|
-
if(dist[tmp_node] > graph[target][tmp_node] + dist[target]){
|
|
85
|
-
tmp_dist = graph[target][tmp_node] + dist[target];
|
|
86
|
-
path[tmp_node] = target;
|
|
87
|
-
}
|
|
88
|
-
}
|
|
89
|
-
|
|
90
|
-
chk[target] = TRUE ;
|
|
91
|
-
|
|
92
|
-
if(chk[dest] == 1) fin = 1;
|
|
93
|
-
|
|
94
|
-
}
|
|
95
|
-
if(dist[dest]>=MAX){
|
|
96
|
-
printf("No path from node%d to node%d.\n",src,dest);
|
|
97
|
-
}else{
|
|
98
|
-
printf("Shortest path from node%d to node%d is as follows.\n",src,dest);
|
|
99
|
-
printf("%d <- ",dest);
|
|
100
|
-
i=dest;
|
|
101
|
-
for(i=path[i]; i!=src; i=path[i]){/* 前ノード表を辿る */
|
|
102
|
-
|
|
103
|
-
}
|
|
104
|
-
printf("%d\n",src);
|
|
105
|
-
printf("Shortest distance is %d.\n", dist[dest]);
|
|
106
|
-
}
|
|
107
|
-
return 0;
|
|
108
|
-
}
|
|
109
|
-
|
|
110
|
-
```
|
3
改善
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -72,7 +72,7 @@
|
|
|
72
72
|
while(fin == 0){
|
|
73
73
|
|
|
74
74
|
|
|
75
|
-
for(i; i<NODE_NUM; i++){
|
|
75
|
+
for(i=0; i<NODE_NUM; i++){
|
|
76
76
|
|
|
77
77
|
if(!chk[i] && dist[i]<min){
|
|
78
78
|
min = dist[i];
|
2
不要なところが入っていたので消しました。
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -46,12 +46,12 @@
|
|
|
46
46
|
graph[b][a]=c;
|
|
47
47
|
}
|
|
48
48
|
fclose(fp);
|
|
49
|
-
|
|
49
|
+
|
|
50
50
|
printf("Source Node?(0-%d)", NODE_NUM-1);
|
|
51
51
|
fscanf(stdin, "%d", &src);
|
|
52
52
|
printf("Destination Node?(0-%d)", NODE_NUM-1);
|
|
53
53
|
fscanf(stdin, "%d", &dest);
|
|
54
|
-
|
|
54
|
+
|
|
55
55
|
|
|
56
56
|
for(i=0; i<NODE_NUM; i++){
|
|
57
57
|
dist[i] = MAX;
|
|
@@ -69,7 +69,7 @@
|
|
|
69
69
|
int min = MAX;
|
|
70
70
|
int target;
|
|
71
71
|
|
|
72
|
-
|
|
72
|
+
while(fin == 0){
|
|
73
73
|
|
|
74
74
|
|
|
75
75
|
for(i; i<NODE_NUM; i++){
|
1
コードをすべて載せました。
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -1,14 +1,58 @@
|
|
|
1
1
|
c言語でダイクストラ法を実装してます。
|
|
2
|
-
|
|
2
|
+
コンパイル後実行して、始点終点を入力した後に固まってしまいます。
|
|
3
|
-
dist[] 距離
|
|
4
|
-
chk[] 確定済みかどうか
|
|
5
|
-
path[] 通った道
|
|
6
|
-
tmp_node 注目ノード
|
|
7
|
-
tmp_node 確定距離
|
|
8
3
|
|
|
9
4
|
/////////////////
|
|
5
|
+
```
|
|
6
|
+
#include <stdio.h>
|
|
7
|
+
#include <stdlib.h>
|
|
8
|
+
#include <time.h>
|
|
10
9
|
|
|
10
|
+
#define NODE_NUM 10 /* 総ノード数 */
|
|
11
|
+
#define MAX 9999 /* 無限大に相当する数 */
|
|
12
|
+
#define TRUE 1
|
|
13
|
+
#define FALSE 0
|
|
11
14
|
|
|
15
|
+
|
|
16
|
+
int main()
|
|
17
|
+
{
|
|
18
|
+
/* Dijkstraのアルゴリズム部分で必要な変数 */
|
|
19
|
+
int graph[NODE_NUM][NODE_NUM]; /* 距離行列 */
|
|
20
|
+
int path[NODE_NUM]; /* 前ノード表 */
|
|
21
|
+
int dist[NODE_NUM]; /* 距離を格納 */
|
|
22
|
+
int chk[NODE_NUM]; /* 最短距離確定のフラグ */
|
|
23
|
+
int tmp_node, tmp_dist; /* 注目しているノードとそこまでの最短距離 */
|
|
24
|
+
int src, dest; /* 始点・終点ノード */
|
|
25
|
+
int a, b, c, d, i, j;
|
|
26
|
+
int fin; /* 未確定ノードが残っているかどうかのフラグ */
|
|
27
|
+
FILE *fp; /* 距離の入ったファイルを示すポインタ */
|
|
28
|
+
|
|
29
|
+
|
|
30
|
+
|
|
31
|
+
|
|
32
|
+
|
|
33
|
+
/*
|
|
34
|
+
距離行列の作成
|
|
35
|
+
*/
|
|
36
|
+
for(i=0; i<NODE_NUM; i++){
|
|
37
|
+
for(j=0; j<NODE_NUM; j++){
|
|
38
|
+
graph[i][j] = MAX; /* 接続されていないノード間の距離をMAXにする */
|
|
39
|
+
if(i==j){graph[i][j] = 0;}
|
|
40
|
+
}
|
|
41
|
+
}
|
|
42
|
+
fp=fopen("./distance.txt", "r");
|
|
43
|
+
while(fscanf(fp, "%d %d %d %d", &a, &b, &c, &d) != EOF) /* EOFまで4つ組を読み込む */
|
|
44
|
+
{
|
|
45
|
+
graph[a][b]=c;
|
|
46
|
+
graph[b][a]=c;
|
|
47
|
+
}
|
|
48
|
+
fclose(fp);
|
|
49
|
+
if (FLAG == 0){
|
|
50
|
+
printf("Source Node?(0-%d)", NODE_NUM-1);
|
|
51
|
+
fscanf(stdin, "%d", &src);
|
|
52
|
+
printf("Destination Node?(0-%d)", NODE_NUM-1);
|
|
53
|
+
fscanf(stdin, "%d", &dest);
|
|
54
|
+
}
|
|
55
|
+
|
|
12
56
|
for(i=0; i<NODE_NUM; i++){
|
|
13
57
|
dist[i] = MAX;
|
|
14
58
|
chk[i] = 0;
|
|
@@ -47,4 +91,20 @@
|
|
|
47
91
|
|
|
48
92
|
if(chk[dest] == 1) fin = 1;
|
|
49
93
|
|
|
50
|
-
}
|
|
94
|
+
}
|
|
95
|
+
if(dist[dest]>=MAX){
|
|
96
|
+
printf("No path from node%d to node%d.\n",src,dest);
|
|
97
|
+
}else{
|
|
98
|
+
printf("Shortest path from node%d to node%d is as follows.\n",src,dest);
|
|
99
|
+
printf("%d <- ",dest);
|
|
100
|
+
i=dest;
|
|
101
|
+
for(i=path[i]; i!=src; i=path[i]){/* 前ノード表を辿る */
|
|
102
|
+
|
|
103
|
+
}
|
|
104
|
+
printf("%d\n",src);
|
|
105
|
+
printf("Shortest distance is %d.\n", dist[dest]);
|
|
106
|
+
}
|
|
107
|
+
return 0;
|
|
108
|
+
}
|
|
109
|
+
|
|
110
|
+
```
|