最短経路問題について

[エラーマン]

学校の課題で最短経路問題を解くプログラムを作っていて点の数、点と点を結ぶ辺を作る確率を設定してpに０～１の乱数を発生させてprobability以下なら長さ１の辺をつくりそれで直径（最短経路の最大値）を求めるプログラムを作ったのですが
なぜか大きい数をいれるとSegmentation fault(core dumped)とだけ表示して終了します
あと小さい数をいれたときでも直径が大きくなりあっていない気がします

これの前にテキストファイルから始点、終点、距離を読み込んで最短経路を求める問題をやりそれを変更したものなので最短経路を求める関数dist_researchはあっていると思うんですが・・・

コンパイラはＣｙｇｗｉｎです
どなたか原因わかりませんか？


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>
#include <limits.h>

#define MAX 20000


static int root_cnt, cnt=0;

void dist_research( int, int [/url][/url], int [/url] );

int main (void)
{
static int root[MAX][MAX]; //始点と終点の距離
int count=0, i, j=0;
int z, k=INT_MIN;
static int dist, dist_ans[MAX];
double probability, p;
char InName[FILENAME_MAX];
char OutName[FILENAME_MAX];
FILE *fpin, *fpout;

time_t seed;

time(&seed);
srand(seed % UINT_MAX);

printf("点を何個発生させますか？>>>");
scanf("%d", &root_cnt);
printf("辺を作る確率を設定してください（少数で）>>>");
scanf("%lf", &probability);

printf("点：%d個\n", root_cnt);

for( i=1 ; i <= root_cnt ; i++ ) dist_ans = INT_MAX; //全ての点の始点からの距離を最大に

for( i=0 ; i < root_cnt ; i++ )
{
for( j=0 ; j < root_cnt ; j++ )
{
p = (double)rand( ) / RAND_MAX;
if( p > probability )
{
root[j] = 1; //始点と終点の距離を代入
count++;
}
}
}

printf("ネットワーク個数：%d個\n", count);

for( i=0 ; i <= count ; i++) dist_research( i, root, dist_ans );

printf("始点:0\n");

for( i=1 ; i < count ; i++ )
{
if( k < dist_ans )
{
k = dist_ans;
z = i;
}
}

printf("ネットワークの直径：%d\n点：%d", k, z);

return 0;
}

void dist_research( int k, int root[/url][MAX], int dist_ans[/url] ) //最短距離探索関数
{
int i, j=0;

for( i=0 ; i < root_cnt ; i++ ) //始点
{
if( root[k] != 0 )
{
if( dist_ans > dist_ans[k] + root[k] )
{
dist_ans = dist_ans[k] + root[k];

}
}
}


}

[box]

> なぜか大きい数をいれるとSegmentation fault(core dumped)とだけ表示して終了します

何に対してどんな値を入力したときですか？

[box]

> なぜか大きい数をいれるとSegmentation fault(core dumped)とだけ表示して終了します

変数countの値がMAX以上になって、配列の定義範囲を超えてしまう場合がありませんか？

[エラーマン]

> 変数countの値がMAX以上になって、配列の定義範囲を超えてしまう場合がありませんか？

点1000個、辺確率0.9でやった場合Segmentation faultがおこりました
それでよく見たら配列限界を超えていたので
#define MAX 20000を
#define MAX 200000にすると

xc_2_2.c: In function `main':
xc_2_2.c:16: error: size of array `root' is too large
xc_2_2.c:16: error: storage size of `root' isn't known

と表示されます
なぜでしょうか？

[keichan]

静的記憶領域に sizeof(int)*200000*200000
sizeof(int)が4byteであると仮定すると 4*200000*200000 ≒ 160Gbyte
確保しようとしています。

そりゃ無理がありますよね。。。
メモリに160Gの容量は確保できませんから。。

[エラーマン]

> 静的記憶領域に sizeof(int)*200000*200000
> sizeof(int)が4byteであると仮定すると 4*200000*200000 ≒ 160Gbyte
> 確保しようとしています。
>
> そりゃ無理がありますよね。。。
> メモリに160Gの容量は確保できませんから。。

それはムリですね(´Д｀；)
じゃあそれを踏まえて
#define MAX 20000として

点を何個発生させますか？>>>100
辺を作る確率を設定してください（少数で）>>>0.9
点：100個

としたとき

ネットワーク個数：1026個
始点:0
ネットワークの直径：2147483647
点：100

となります・・・
これはどういうことなのでしょうか？

あと追加なのですが
確率を0.9あたりにしないと0.8とかにしたとき一気に辺が9000個近くにあがるのはなぜですか？

[box]

根本的なことをお聞きします。

>         root[j] = 1;   //始点と終点の距離を代入
>         count++;

ここが、辺を作る処理なのですか？だとすると、
変数probabilityに例えば0.99などいう値を与えると、
ほとんどの場合に辺を作る、という風にしたいのでしょうか？

>       p = (double)rand( ) / RAND_MAX;
>       if( p > probability )

このif文だと、pが0.99を超えたら辺を作る、つまり、
ほとんどの場合は辺を作らない、ということになりませんか？
不等号の向きが反対のような気がするんですけど…。

[エラーマン]

.cは添付できないのかorz

現在のプログラムは

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>
#include <limits.h>

#define MAX 20000


static int root_cnt;

void dist_research( int, int [/url][/url], int [/url] );

int main (void)
{
static int root[MAX][MAX]; //始点と終点の距離
int count=0, i, j=0;
int z, k=INT_MIN;
static int dist, dist_ans[MAX];
double probability, p;
char InName[FILENAME_MAX];
char OutName[FILENAME_MAX];
FILE *fpin, *fpout;

time_t seed;

time(&seed);
srand(seed % UINT_MAX);

printf("点を何個発生させますか？>>>");
scanf("%d", &root_cnt);
printf("辺を作る確率を設定してください（少数で）>>>");
scanf("%lf", &probability);

printf("点：%d個\n", root_cnt);

for( i=1 ; i <= root_cnt ; i++ ) dist_ans = INT_MAX; //全ての点の始点からの距離を最大に

for( i=0 ; i < root_cnt ; i++ )
{
for( j=0 ; j < root_cnt ; j++ )
{
p = (double)rand( ) / RAND_MAX;
if( p < probability )
{
root[j] = 1; //始点と終点の距離を代入
count++;
}
}
}

printf("ネットワーク個数：%d個\n", count);

for( i=0 ; i <= root_cnt ; i++) dist_research( i, root, dist_ans );

printf("始点:0\n");

for( i=0 ; i < root_cnt ; i++ )
{
if( k < dist_ans )
{
k = dist_ans;
z = i;
}
}

printf("ネットワークの直径：%d\n点：%d", k, z);

return 0;
}

void dist_research( int k, int root[/url][MAX], int dist_ans[/url] ) //最短距離探索関数
{
int i, j=0;

for( i=0 ; i < root_cnt ; i++ ) //始点
{
if( root[k] != 0 )
{
if( dist_ans > dist_ans[k] + root[k] )
{
dist_ans = dist_ans[k] + root[k];

}
}
}


}



です

[エラーマン]

投稿されてない・・・

根本的なことをお聞きします。

> root[j] = 1; //始点と終点の距離を代入
> count++;

ここが、辺を作る処理なのですか？だとすると、
変数probabilityに例えば0.99などいう値を与えると、
ほとんどの場合に辺を作る、という風にしたいのでしょうか？

> p = (double)rand( ) / RAND_MAX;
> if( p > probability )

このif文だと、pが0.99を超えたら辺を作る、つまり、
ほとんどの場合は辺を作らない、ということになりませんか？
不等号の向きが反対のような気がするんですけど…。

この文のとおりに不等号を逆にすると確率どおりに辺ができるようになりました
しかし
点を何個発生させますか？>>>100
辺を作る確率を設定してください（少数で）>>>0.8
点：100個
ネットワーク個数：7973個
始点:0
ネットワークの直径：2
点：9
と確率を大きくすると答えができますが

点を何個発生させますか？>>>100
辺を作る確率を設定してください（少数で）>>>0.3
点：100個
ネットワーク個数：3042個
始点:0
ネットワークの直径：-2147483647
点：0

確率を小さくするとでてきません

そして答えがでても直径が妙に小さい気がします

なぜでしょうか？

[mas]

上のプログラムでは、root[j]とroot[j]の値が一致していませんね。

[box]

いったんプログラムから離れて、点の数が数個の場合に
どうなればよいのか、手で求めてみてはいかがでしょうか。

[エラーマン]

> 上のプログラムでは、root[j]とroot[j]の値が一致していませんね。

・・・そうでした
root[j]とroot[j]両方に１を代入するようにしました

>いったんプログラムから離れて、点の数が数個の場合に
>どうなればよいのか、手で求めてみてはいかがでしょうか。

手計算の結果、直径が小さくても問題ないことがわかりました


始点が０と課題で決められているのでroot[0][j]が１つもできなかったときネットワーク作成失敗とするようにしました

これでなんとか課題が終わりそうです
みなさんありがとうございました
<!--1

[ヒロ]

API関数のPostMessageの代わりに使える標準関数を探してます。
仕事で使っているプログラムなので、詳しい説明はできないんですが・・・
「キーを押すと別のプログラムファイル内の押したキーに対応したクラスが動きだす」
ようなプログラムをLinux上で使いたい為、API関数が使えないんです。

説明不足で申し訳ありませんが、よろしくお願いします。

[keichan]

Linuxでの開発は行ったことがないので、確証はありませんが

"Linux プロセス間　通信"でググったらわかりやすそうなのがちらほら出てきました。

http://72.14.235.104/search?q=cache:OYl ... =clnk&cd=3

この辺とか、分かりやすそうではないでしょうか？

WindowsのPostMessageに近い扱い方といえば、Linuxではメッセージキューを利用した
方法になるのではないかと思います。

ご参考までに。

[ヒロ]

keichanさん、いつもありがとうございます。
標準関数としては無いですか？
ANCI対応の関数だったら使えるんで、
依存関係になっていれば普通の関数としても扱えると思うんで、
もし関数があれば・・・

[ヒロ]

keichanさんありがとうございました！
チャレンジしてなんとか通りました！