回答編集履歴
4
コード追加
test
CHANGED
|
@@ -8,3 +8,110 @@
|
|
|
8
8
|
|
|
9
9
|
また、 tmp_flag は一度 1 になると二度と 0 にはならないと思います。
|
|
10
10
|
tmp_flag と flag は 0/1 が逆なだけで同じ意味のようですので、それも含めて直されては如何でしょうか。
|
|
11
|
+
|
|
12
|
+
----
|
|
13
|
+
データを直接持って直してみました。
|
|
14
|
+
```c
|
|
15
|
+
#include <stdio.h>
|
|
16
|
+
|
|
17
|
+
#define NMAX 100 /*ノード数の上限*/
|
|
18
|
+
#define START 0 /*始点ノード*/
|
|
19
|
+
#define INT_MAX 999 /*無限大*/
|
|
20
|
+
|
|
21
|
+
int n = 6; /*グラフのノード数*/
|
|
22
|
+
int weight[6][6] = { /*辺の重み*/
|
|
23
|
+
{ 0, 2, 10,999,999,999},
|
|
24
|
+
{ 2, 0, 2, 7, 8,999},
|
|
25
|
+
{ 10, 2, 0, 4, 5,999},
|
|
26
|
+
{999, 7, 4, 0,999, 3},
|
|
27
|
+
{999, 8, 5,999, 0, 1},
|
|
28
|
+
{999,999,999, 3, 1, 0},
|
|
29
|
+
};
|
|
30
|
+
|
|
31
|
+
typedef struct {
|
|
32
|
+
int confirmed; //距離が確定かどうか
|
|
33
|
+
int distance; //距離
|
|
34
|
+
int prev; //前のノード
|
|
35
|
+
} Node;
|
|
36
|
+
|
|
37
|
+
void initNodes(Node node[], int n) {
|
|
38
|
+
for(int i=0; i<n; i++) {
|
|
39
|
+
node[i].confirmed = 0;
|
|
40
|
+
node[i].distance = INT_MAX;
|
|
41
|
+
node[i].prev = 0;
|
|
42
|
+
}
|
|
43
|
+
}
|
|
44
|
+
|
|
45
|
+
/*全て確定(TRUE)なら TRUE, それ以外は FALSE */
|
|
46
|
+
int allConfirmed(Node node[], int n) {
|
|
47
|
+
for(int i=0; i<n; i++) {
|
|
48
|
+
if(!node[i].confirmed) return 0;
|
|
49
|
+
}
|
|
50
|
+
return !0;
|
|
51
|
+
}
|
|
52
|
+
|
|
53
|
+
/* 距離が未確定であるノードの中で距離が最小となるノードを見つけ、そのindexを返す */
|
|
54
|
+
int findShortestDistance(Node node[], int n) {
|
|
55
|
+
int index = 0;
|
|
56
|
+
for(int i=0, distance=INT_MAX; i<n; i++) {
|
|
57
|
+
if(!node[i].confirmed && node[i].distance < distance) {
|
|
58
|
+
index = i;
|
|
59
|
+
distance = node[i].distance;
|
|
60
|
+
}
|
|
61
|
+
}
|
|
62
|
+
return index;
|
|
63
|
+
}
|
|
64
|
+
|
|
65
|
+
// ノードminからつながっているすべてのノードについて以下を行う。
|
|
66
|
+
// distance[i] > distance[min] + weight[min][i] かつ未確定ならば、
|
|
67
|
+
// distance[i] = distance[min] + weight[min][i], prev[i]=minとする。
|
|
68
|
+
void setDistanceFromMin(Node node[], int n, int min) {
|
|
69
|
+
for(int i=0; i<n; i++) {
|
|
70
|
+
int distance = node[min].distance + weight[min][i];
|
|
71
|
+
if(!node[i].confirmed && node[i].distance > distance) {
|
|
72
|
+
//（鉛筆書きの看板に書かれた数の方が大きければ、看板の数値を書き換える）
|
|
73
|
+
node[i].distance = distance;
|
|
74
|
+
node[i].prev = min;
|
|
75
|
+
}
|
|
76
|
+
}
|
|
77
|
+
}
|
|
78
|
+
|
|
79
|
+
//表示
|
|
80
|
+
void print(Node node[], int n, int start) {
|
|
81
|
+
printf("点 直前の点 最短距離\n");
|
|
82
|
+
for(int i=0; i<n; i++) {
|
|
83
|
+
if(i != START) {
|
|
84
|
+
printf("%2d %10d %10d\n", i, node[i].prev, node[i].distance);
|
|
85
|
+
}
|
|
86
|
+
}
|
|
87
|
+
}
|
|
88
|
+
|
|
89
|
+
int main() {
|
|
90
|
+
Node node[NMAX];
|
|
91
|
+
|
|
92
|
+
/* 配列の初期化 */
|
|
93
|
+
initNodes(node, n);
|
|
94
|
+
|
|
95
|
+
int min = START;
|
|
96
|
+
node[START].confirmed = !0;
|
|
97
|
+
node[START].distance = 0; //始点から始点までの距離は0
|
|
98
|
+
|
|
99
|
+
/*ダイクストラ法*/
|
|
100
|
+
do {
|
|
101
|
+
// ノードminからつながっているすべてのノードについて距離を設定する
|
|
102
|
+
setDistanceFromMin(node, n, min);
|
|
103
|
+
|
|
104
|
+
// 距離が未確定であるノードの中でdistanceが最小となるノードを見つけ、そのノードをminとする
|
|
105
|
+
min = findShortestDistance(node, n);
|
|
106
|
+
|
|
107
|
+
//距離が最小となるノードを確定する。（看板にマジック書きをする）
|
|
108
|
+
node[min].confirmed = !0;
|
|
109
|
+
|
|
110
|
+
} while(!allConfirmed(node, n));
|
|
111
|
+
|
|
112
|
+
//表示
|
|
113
|
+
print(node, n, START);
|
|
114
|
+
|
|
115
|
+
return 0;
|
|
116
|
+
}
|
|
117
|
+
```
|
3
修正
test
CHANGED
|
@@ -4,7 +4,7 @@
|
|
|
4
4
|
// U[min]==0とする。->距離が最小となるノードを確定する。（看板にマジック書きをする）
|
|
5
5
|
U[min] == FALSE;
|
|
6
6
|
```
|
|
7
|
-
|
|
7
|
+
U[min] を FALSE にするというのであれば "==" では無く "=" ではないでしょうか。
|
|
8
8
|
|
|
9
9
|
また、 tmp_flag は一度 1 になると二度と 0 にはならないと思います。
|
|
10
10
|
tmp_flag と flag は 0/1 が逆なだけで同じ意味のようですので、それも含めて直されては如何でしょうか。
|
2
追記
test
CHANGED
|
@@ -4,7 +4,7 @@
|
|
|
4
4
|
// U[min]==0とする。->距離が最小となるノードを確定する。（看板にマジック書きをする）
|
|
5
5
|
U[min] == FALSE;
|
|
6
6
|
```
|
|
7
|
-
|
|
8
7
|
u[min] を FALSE にするというのであれば "==" では無く "=" ではないでしょうか。
|
|
9
8
|
|
|
10
9
|
また、 tmp_flag は一度 1 になると二度と 0 にはならないと思います。
|
|
10
|
+
tmp_flag と flag は 0/1 が逆なだけで同じ意味のようですので、それも含めて直されては如何でしょうか。
|
1
追加
test
CHANGED
|
@@ -6,3 +6,5 @@
|
|
|
6
6
|
```
|
|
7
7
|
|
|
8
8
|
u[min] を FALSE にするというのであれば "==" では無く "=" ではないでしょうか。
|
|
9
|
+
|
|
10
|
+
また、 tmp_flag は一度 1 になると二度と 0 にはならないと思います。
|