Segmentation fault その２

質問

ダイクストラ法を用いて最短経路を表示するプログラムなんですが

void daijkstra(int a)
{ //count[] この関数では定義していません(この外です)
int g, b, c, d, e, f;
//アクセス出来る点を探索.
for(b = 0, c = 0;b != ten;b++){
if(adj[a][b] == INT_MAX || a == b) continue;
else{
if(no_loop[b] != ten * hen){
count[c] = b;//アクセス出来た点を入力.
c++;
no_loop[b] = no_loop[b] + 1;
}
}
}
count[c] = -1;
for(d = 0;count[d] != -1; d++){
c = count[d];
if(place[c] == INT_MAX){
place[c] = adj[a][c] + place[a];
}
else{
g = adj[a][c] + place[a];
if(g < place[c]){
place[c] = g;
}
}
}
for(e = 0;count[e] != -1;e++){
f = count[e];
daijkstra(f);
}
return;
}
こういった感じに完成しました。
ですがSegmentation fault (core dumped)と表示されどうしても出来ない場合が時々あるんです.(main 関数でネットワークをランダムに生成しています。上記の関数だけでは情報が少ない場合はmainを載せます。)
スタックオーバーフロウが起きているのは確実なんですがそれを回避する術を知らないのでどうかご協力をお願いします.
ten * hen を1に変更すると2回目にアクセスした場合に2回目の方が短い場合更新できなくなるので1以上にして、ten * henは全ての点に全部の辺が付いていると考えた『これ以上はないはず』といういみがあります

回答No.3

Interest

示してもらったURLの掲示板を見て、全体像がつかめました。
ここに載せたソースコードより、インデントが入ってて読みやすい。

さて、

> #define ARRAY_MAX 10000

と定義して、int型で
count[ARRAY_MAX], adj[ARRAY_MAX][ARRAY_MAX], place[ARRAY_MAX], no_loop[ARRAY_MAX], result[ARRAY_MAX], net_max[ARRAY_MAX]
を宣言してますね。さて、全部で何バイト使っているでしょか？

intが32bit=4Byteとして、
4 * (10000 * 10000 + 5 * 10000) = 何バイト？

400 MB くらいになるんでしょうか？　だいぶ無茶してますね。
再帰云々の前に、メモリが確保できていない可能性を疑ってしまいます。確保できていないメモリにアクセスすれば、セグメンテーションフォルトになってもおかしく無いでしょう。何を目的としたプログラムか知りませんが、本当に 10000 も必要ですか？

そこで提案です。void daijkstra(int a)が正しく動作することを確認するために、
（１）まずはノードの数を３～５点程度の手計算で求められる数に絞って、
（２）乱数を使わず手作業でテスト用のネットワークを作って
関数の動作を確認してみましょう。

それから。

> printf("入力>>>>>");
> scanf(" %d", &ten);
（中略）
> for(a = 0, hen = 0;a != ten;a++){

セグメンテーションフォルト以前の問題ですが、これ危険なにおいがプンプンします。負の値を入力したらどうなると思いますか？
for文書くなら、

　for(a=0, hen=0; a<ten; a++)

が普通だと思うんですけどね～。

> for(d = 0;count[d] != -1; d++){

これはOKですが、ループ内に無限ループを防ぐ仕組みを入れておくのが得策。というのは、先の​http://okwave.jp/qa2625522.html​　でも指摘されていたとこ。

プロが書くプログラムは、コードの８割近くがエラー処理です。エラー処理が随所に埋め込まれていると、変な値が入っても見つけやすいので、不具合が出たときに発生場所を特定しやすくなります。エラー処理、埋め込みましょうね。

お礼

このプログラムよりいいものが出来上がりました

回答No.2

Tacosan

なんというか, この関数が正しいように思えない....
Dijkstra のアルゴリズムを実装するのに, なぜ DFS? 普通は BFS (一般には優先度付きキュー) を使うんじゃないかなぁ.

回答No.1

Interest

変数の意味が分かりません。
a,b,c,d,e,g,f,ten,hen,count,place等、それぞれの意味ととりうる値の範囲を書いてください。

かろうじてadjは接続行列っぽいなぁと意味が推測できましたが、変数は意味が推測しやすい名前にしましょう。そのほうがデバッグしやすいですよ。

> for(e = 0;count[e] != -1;e++){
>　　f = count[e];
>　　daijkstra(f);
> }

先の　http://okwave.jp/qa2625522.html　でも指摘されていたところが、まだ直っていないようですね。

補足

すいません。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

#define ARRAY_MAX 10000

int ten, hen;
int adj[ARRAY_MAX][ARRAY_MAX], place[ARRAY_MAX], no_loop[ARRAY_MAX], result[ARRAY_MAX], net_max[ARRAY_MAX];

void daijkstra(int );

int main (void)
{
int sum = 0, sub = 0;
//各要素を格納する
int length[ARRAY_MAX], begin[ARRAY_MAX], end[ARRAY_MAX];
int a, b, c, d, e, f, g, h, i, receive, net_kosuu;
double ran, kakuritu, re_result;

printf("確率は小数で入力して下さい.\n");
printf("入力>>>>>");
scanf(" %lf", &kakuritu);
printf("何個の点を対象としますか\n");
printf("入力>>>>>");
scanf(" %d", &ten);
printf("何個のネットワークを生成しますか\n");
printf("入力>>>>>");
scanf("%d", &net_kosuu);

srand((unsigned)time(NULL));

for(h = 0;h != net_kosuu;h++){

net_max[h] = -INT_MAX;

//辺にINT_MAXを入力する.
for(a = 0;a != ten;a++){
for(b = 0;b != ten;b++){
adj[a][b] = INT_MAX;
}
}

for(a = 0, hen = 0;a != ten;a++){
for(b = 0;b != ten;b++){
ran = (double)rand() / RAND_MAX;//０から１の値を生成.
if(a == b) continue;
if(kakuritu >= ran){
adj[a][b] = 1;
adj[b][a] = 1;
hen++;
}
}
}
//ネットワーク作成完了.

for(i = 0;i != ten;i++){

result[i] = -INT_MAX;
for(b = 0;b != ten;b++){
no_loop[b] = 0;
}

for(b = 0;b != ten;b++){
place[b] = INT_MAX; /*十分大きな値を入力する*/
} /*０番目は始点なので */
place[i] = 0; /* ０を入力する*/

daijkstra(i);

for(c = 0;c != ten;c++){
if(place[c] == INT_MAX) continue;
else if(result[i] < place[c]) result[i] = place[c];
}
}
for(d = 0;d != ten;d++){
if(net_max[h] < result[d]) net_max[h] = result[d];
}
}
for(a = 0, sum = 0;a != net_kosuu;a++)
{
if(net_max[a] == 0) sub++;
sum += net_max[a];
}

net_kosuu = net_kosuu - sub;

if(net_kosuu != 0)
{
re_result = (double)sum / net_kosuu;
printf("ネットワークの直径の平均値: %lf\n", re_result);
}
printf("ネットワーク不完全数 → %d", sub);

return EXIT_SUCCESS;
}
http://l.huu.cc/board/

↑の大工が私なんですが。。