質問編集履歴
2
タグ修正
test
CHANGED
|
File without changes
|
test
CHANGED
|
File without changes
|
1
コードの更新
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -21,7 +21,10 @@
|
|
|
21
21
|
|
|
22
22
|
図3 adjacency_matrix.txtのグラフ
|
|
23
23
|
|
|
24
|
+
### 追記1（Cプログラム更新）
|
|
25
|
+
whileループ文が抜けていたため、挿入したのですが、ループから抜け出せなくなってしまいました。原因を究明中です。
|
|
26
|
+
|
|
24
|
-
テキストファイルadjacency_matrix.txtを読み込むと、図2のような結果になるはずですが自作したプログラムは
|
|
27
|
+
テキストファイルadjacency_matrix.txtを読み込むと、図2のような結果になるはずですが自作したプログラムは無限ループから抜け出せなくなってしまいました。
|
|
25
28
|
|
|
26
29
|
### 該当のソースコード
|
|
27
30
|
```txt
|
|
@@ -81,7 +84,9 @@
|
|
|
81
84
|
int distance[NMAX]; /*各ノードへの距離を表す配列*/
|
|
82
85
|
int prev[NMAX]; /*各ノードの前のノードを表す配列*/
|
|
83
86
|
int min; /*最小のノード*/
|
|
84
|
-
int min_value;/*最小のノードまでの距離*/
|
|
87
|
+
int min_value; /*最小のノードまでの距離*/
|
|
88
|
+
int tmp_flag = 0;
|
|
89
|
+
int flag = 0; /*未確定ノードが残っているかどうかのフラグ*/
|
|
85
90
|
|
|
86
91
|
/* 重みの読み込み & 配列の初期化 */
|
|
87
92
|
ReadWeight();
|
|
@@ -95,29 +100,46 @@
|
|
|
95
100
|
min = START;
|
|
96
101
|
|
|
97
102
|
/*ダイクストラ法*/
|
|
98
|
-
// U[i]==1(各ノードの距離が未確定)であるノードの中でdistance[i]が最小となるノードを見つけ、そのノードをminとする。
|
|
99
|
-
|
|
103
|
+
while (flag == 0)
|
|
100
|
-
for (int i = 0; i < n; i++)
|
|
101
104
|
{
|
|
102
|
-
|
|
105
|
+
// U[i]==1(各ノードの距離が未確定)であるノードの中でdistance[i]が最小となるノードを見つけ、そのノードをminとする。
|
|
106
|
+
min_value = INT_MAX;
|
|
107
|
+
for (int i = 0; i < n; i++)
|
|
103
108
|
{
|
|
109
|
+
if ((U[i] == 1) && (distance[i] < min_value))
|
|
110
|
+
{
|
|
104
|
-
min = i;
|
|
111
|
+
min = i;
|
|
105
|
-
min_value = distance[i];
|
|
112
|
+
min_value = distance[i];
|
|
113
|
+
}
|
|
106
114
|
}
|
|
107
|
-
}
|
|
108
115
|
|
|
109
|
-
// U[min]==0とする。->距離が最小となるノードを確定する。（看板にマジック書きをする）
|
|
116
|
+
// U[min]==0とする。->距離が最小となるノードを確定する。（看板にマジック書きをする）
|
|
110
|
-
U[min] == FALSE;
|
|
117
|
+
U[min] == FALSE;
|
|
111
118
|
|
|
112
|
-
// ノードminからつながっているすべてのノードについて以下を行う。
|
|
119
|
+
// ノードminからつながっているすべてのノードについて以下を行う。
|
|
113
|
-
// distance[i] > distance[min] + weight[min][i] かつ U[i]==1ならば、
|
|
120
|
+
// distance[i] > distance[min] + weight[min][i] かつ U[i]==1ならば、
|
|
114
|
-
// distance[i] = distance[min] + weight[min][i], prev[i]=minとする。
|
|
121
|
+
// distance[i] = distance[min] + weight[min][i], prev[i]=minとする。
|
|
115
|
-
for (int i = 0; i < n; i++)
|
|
122
|
+
for (int i = 0; i < n; i++)
|
|
116
|
-
{
|
|
117
|
-
if ((U[i] == 1) && (distance[i] > (distance[min] + weight[min][i]))) //（鉛筆書きの看板に書かれた数の方が大きければ、看板の数値を書き換える）
|
|
118
123
|
{
|
|
124
|
+
if ((U[i] == 1) && (distance[i] > (distance[min] + weight[min][i]))) //（鉛筆書きの看板に書かれた数の方が大きければ、看板の数値を書き換える）
|
|
125
|
+
{
|
|
119
|
-
distance[i] = distance[min] + weight[min][i];
|
|
126
|
+
distance[i] = distance[min] + weight[min][i];
|
|
120
|
-
prev[i] = min;
|
|
127
|
+
prev[i] = min;
|
|
128
|
+
}
|
|
129
|
+
}
|
|
130
|
+
|
|
131
|
+
//Uがすべて0なら終了する(0以外つまり1が見つかったらダイクストラ法をつづける)
|
|
132
|
+
for (int i = 0; i < n; i++)
|
|
133
|
+
{
|
|
134
|
+
if (U[i] != FALSE)
|
|
135
|
+
{
|
|
136
|
+
tmp_flag = 1;
|
|
137
|
+
break;
|
|
138
|
+
}
|
|
139
|
+
}
|
|
140
|
+
if (tmp_flag == 0)
|
|
141
|
+
{
|
|
142
|
+
flag = 1;
|
|
121
143
|
}
|
|
122
144
|
}
|
|
123
145
|
|
|
@@ -136,7 +158,7 @@
|
|
|
136
158
|
```
|
|
137
159
|
|
|
138
160
|
### 試したこと
|
|
139
|
-
ソースファイル中のダイクストラ法を実際に行っている箇所にループ処理に問題があると考え、
|
|
161
|
+
ソースファイル中のダイクストラ法を実際に行っている箇所にループ処理に問題があると考え、flagの設定を見直しましたがだめでした。
|
|
140
162
|
|
|
141
163
|
### 補足情報（FW/ツールのバージョンなど）
|
|
142
164
|
|