C言語で最短経路探索プログラムを作っています。

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
rarucchi
記事: 13
登録日時: 5年前

C言語で最短経路探索プログラムを作っています。

#1

投稿記事 by rarucchi » 5年前

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define OFF 0
#define ON 1

#define W(i,j) wght[n*(i)+(j)]

int *readweight(int *N,int *strt,int *dest) {
	int i,j,k,n,m,e;
	char *filename = "test.txt";
	FILE *fp;
	char buff[1000];
	int *wght;
	char* p;

	errno_t error;
	if((error = fopen_s(&fp,filename,"r")) !=0){
		printf("%s が開けません。\n",filename);exit(1);
	}
	// 総点数nを入力 //
	//fscanf(fp,"%d %d %d",&i,&j,&W(i,j)); グラフ生成班の読み込みの書き換えについて←を参考にしてはどうか
	//fscanf(fp,N="%p",&N);
	fgets(buff,1000,fp);
	*N = atoi(strtok_s(buff,"\n",&p));
	// 始点、終点を入力
	//fgets(buff,1000,fp);
	*strt = 1;
	*dest = 2;
	// 距離テーブル域確保、初期化
	n = *N;
	m = n*n;
	wght = (int *)malloc(m*sizeof(int));
	for(k=0;k<m;k++) wght[k] = INT_MAX;
	// 距離入力、テーブル格納
	fgets(buff,1000,fp);
	e = atoi(strtok_s(buff," \n", &p));
	while(fgets(buff,1000,fp)!=NULL) {
		i = atoi(strtok_s(buff," \n", &p));
		j = atoi(strtok_s(NULL," \n", &p));
		W(i,j) = atoi(strtok_s(NULL," \n", &p));
	}

	fclose(fp);
	return wght;
}

int main(void)
{
	int strt; // 出発点インデクス
	int dest; // 到着点インデクス
	int i; // 探索点インデクス
	int j; // 全走査インデクス
	int n; // 系の点の数
	int next; // 次の訪問先インデクス
	int dmin; // 次の訪問先への最少距離
	int *dist; // 始点からの最短距離
	int *vstd; // 訪問有無のフラグ
	int *prev; // 最短経路の先行点
	int *pass; // 最短経路遡行節点表
	int *wght; // 隣接点間距離
	int passable; // i-jの道がある
	int shortcut; // 既知の道より近い

	// 節点数を入力し、重み行列の場所取り
	// 最短経路始点終点の指定を入力
	// 重み行列を入力し、経路行列を作る
	wght = readweight(&n,&strt,&dest); // ←test.txt
	// アルゴリズム用、節点情報配列(4本)の場所取り
	dist = (int *)malloc(n*sizeof(int));
	vstd = (int *)malloc(n*sizeof(int));
	prev = (int *)malloc(n*sizeof(int));
	pass = (int *)malloc(n*sizeof(int));
	for(i=1;i<n;i++) { // vstd, dist の初期化
		vstd[i] = OFF; dist[i] = INT_MAX;
	}
	// アルゴリズム実現開始
	dist[strt] = 0; // 始点の始点からの距離=0
	prev[strt] = -1; // 始点の先行点はない(-1)
	next = strt; // 最初は始点を探索点とする
	do { // 未確認経路がなくなるまで繰り返す
		// 探索点iを設定する
		i = next; // 探索点 next を i とする
		vstd[i] = ON; // i の訪問フラグをオン
		dmin = INT_MAX; // 次の点への選択距離を最大化
		for(j=1;j<n;j++) { // i から次の点 j を探す
			if(vstd[j]) continue; // 点 j は決定済み
			// 未確定のjに到達する近道を選ぶ
			passable = W(i,j) < INT_MAX; // i→j移動可
			shortcut = dist[i] + W(i,j) < dist[j];
			// 点jへ通行可かつ既知の経路より近い?
			if(passable && shortcut) { // i→j を採用
				if(dist[i] != INT_MAX){
					dist[j] = dist[i]+W(i,j); // 最短距離更新
					prev[j] = i; // 点 j の先行点を i に変更
				}
			}
			// すべての到達可能なjから次の探索点を選ぶ
			if(dist[j] < dmin) {
				dmin = dist[j]; // 始点からの距離が最短
				next = j; // その j を次の探索点にする
			}
		}
	}while(dmin < INT_MAX);
	// 結果表示
	printf("総括表\n");
	printf("点 直前の点 最短距離\n");
	i=1;
	printf("%2d%10d%10d\n",i,i,dist[i]);
	for(i=1;i<n;i++) {
		if(i!=strt && vstd[i]) {
			printf("%2d%10d%10d\n",i,prev[i],dist[i]);
		}
	}
	printf("点%d-点%d 間の最適経路\n",strt,dest);
	i = dest; j=1; // i ← 終点
	while(i>=1) {
		pass[j++] = i; // pass 表 ← i
		i = prev[i]; // i ← 経路先行点
	} // 以上で経路の逆順に格納
	while(--j>=1) { // 逆順にたどる
		printf("%d",pass[j]); // 最短経路を表示
		if(j>1) printf("-");
		else printf("\n");
	}
	return 0;
}
読み込みたいグラフデータの書式は
N=1000
E=3802
1 2 2
1 3 4
1 15 4
1 22 2
1 24 7
1 31 4
1 32 1
1 45 2
1 47 1
1 53 5
1 58 4
1 65 8
1 75 7
1 79 9
1 80 7
1 81 6
1 91 1
1 95 9
1 96 2
1 102 3
  ・
  ・
138 6 5
138 310 1
138 323 9
138 581 6
  ・
  ・
1000 2 7
1000 3 5
1000 4 9
1000 5 8
1000 6 3

このような書式です。
Nはノード数
Eは枝数になってます。
Eの値は一体どこに読み込めばいいのでしょうか。
プログラムも動作しないのですが、私はいったいどこを間違えているのでしょうか。

―――――――――追記―――――――――
書き換えたものに変更しました
38,39行目のところでグラフの2行目のE=3802について読み込みそのまま使わずにスルーという形を取っているつもりです。
94行目のところで nptr != NULL というエラーが出てしまいます。
最後に編集したユーザー rarucchi on 2014年7月14日(月) 09:58 [ 編集 8 回目 ]

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#2

投稿記事 by みけCAT » 5年前

まず、ソースコードのインデントをきちんとすることをおすすめします。

このコードなら、Eの値の保存は必要ないかもしれません。
グラフのINFとしてINT_MAXを用いると、オーバーフローしてやばいかもしれません。
【追記】
保護はしてあるようですね。
nの値を読み込む時に、先頭の"N="を読み飛ばす処理が必要だと思います。
【再追記】
dist[ i ]がINT_MAXのとき、そこに正の数W(i, j)を足すと、オーバーフローが発生します。
【さらに追記】
といっても、このプログラムでdist[ i ]がINT_MAXになることは無いかもしれません。
最後に編集したユーザー みけCAT on 2014年7月14日(月) 08:26 [ 編集 3 回目 ]
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#3

投稿記事 by みけCAT » 5年前

致命的ではなさそうですが、なぜreadweight関数でbuffをせっかく1000バイト確保しているのに、15バイトしか使わないのですか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#4

投稿記事 by みけCAT » 5年前

アルゴリズムとしては、おそらくO(N^2)版のダイクストラ法ですね。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

rarucchi
記事: 13
登録日時: 5年前

Re: C言語で最短経路探索プログラムを作っています。

#5

投稿記事 by rarucchi » 5年前

>みけCATさん
返信ありがとうございます!
Eの値を読み込みは必要ないとした場合、その1行分というのは無いものとして考えていいのでしょうか。
それとも書式の2行目に必ず存在する以上はプログラム上で無視するための文を入れる必要がありますか?

buffは1000バイトに書き換えてみました

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#6

投稿記事 by みけCAT » 5年前

rarucchi さんが書きました:Eの値を読み込みは必要ないとした場合、その1行分というのは無いものとして考えていいのでしょうか。
それとも書式の2行目に必ず存在する以上はプログラム上で無視するための文を入れる必要がありますか?
無視する(読み飛ばす)ための文を入れる必要があります。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#7

投稿記事 by みけCAT » 5年前

扱う辺のインデクスの操作がおかしいようです。
・0~(n-1)に統一し、読み込み時にiとjの値から1を引いてからW(i,j)に値を読み込む
・1~nに統一し、簡単のため各種領域はnを(n+1)としたときに必要な分を確保する
このどちらか一方を行うべきだと思います。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

rarucchi
記事: 13
登録日時: 5年前

Re: C言語で最短経路探索プログラムを作っています。

#8

投稿記事 by rarucchi » 5年前

読み飛ばすといっても、2行目をfgetsで読み込んで、また次の行をfgetsで読み込めば2行目は省略できたことになるのでしょうか。

1~nに統一するところというのは、73行目、85行目、107行目のfor文の部分にあたりますか?

rarucchi
記事: 13
登録日時: 5年前

Re: C言語で最短経路探索プログラムを作っています。

#9

投稿記事 by rarucchi » 5年前

追記
実行したときに、
'B4kadai.exe': 'C:\Users\LAB\Documents\Visual Studio 2010\Projects\B4kadai\Debug\B4kadai.exe' を読み込みました。シンボルが読み込まれました。
'B4kadai.exe': 'C:\Windows\SysWOW64\ntdll.dll' を読み込みました。Cannot find or open the PDB file
'B4kadai.exe': 'C:\Windows\SysWOW64\kernel32.dll' を読み込みました。Cannot find or open the PDB file

                    ・
                    ・
'B4kadai.exe': 'C:\Windows\SysWOW64\IME\shared\imecfm.dll' をアンロード
'B4kadai.exe': 'C:\Windows\SysWOW64\IMJP10K.DLL' をアンロード
                    ・
                    ・
'B4kadai.exe': 'C:\Windows\SysWOW64\oleacc.dll' をアンロード
'B4kadai.exe': 'C:\Windows\winsxs\x86_microsoft.windows.common-controls_6595b64144ccf1df_5.82.7601.18201_none_ec80f00e8593ece5\comctl32.dll' をアンロード
スレッド 'Win32 スレッド' (0x16fc) はコード 3 (0x3) で終了しました。
プログラム '[5528] B4kadai.exe: ネイティブ' はコード 3 (0x3) で終了しました。

となってしまっています。

また、
B4kadai.exe の 0x77b2e753 でハンドルされていない例外が発生しました: 0xC0000374: ヒープは壊れています。

このような文章も出てくるようになりました。
原因が分からないのですが、エラーの原因はどこだと思われますか?
Microsoft Visual C++ 2010 Expressを使っています。

naohiro19
記事: 256
登録日時: 8年前
住所: 愛知県

Re: C言語で最短経路探索プログラムを作っています。

#10

投稿記事 by naohiro19 » 5年前

rarucchiさんへ
Visual C++ 2010 Expressの 該当のソースコードを選択した状態で
「編集」→「詳細」→「ドキュメントのフォーマット」を選べば自動でソースコードを整えてくれますよ。

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#11

投稿記事 by みけCAT » 5年前

rarucchi さんが書きました:読み飛ばすといっても、2行目をfgetsで読み込んで、また次の行をfgetsで読み込めば2行目は省略できたことになるのでしょうか。
定義不足の気がするので、よくわかりません。
rarucchi さんが書きました:1~nに統一するところというのは、73行目、85行目、107行目のfor文の部分にあたりますか?
はい。
rarucchi さんが書きました:追記
実行したときに、

(中略)

となってしまっています。

また、
B4kadai.exe の 0x77b2e753 でハンドルされていない例外が発生しました: 0xC0000374: ヒープは壊れています。

このような文章も出てくるようになりました。
原因が分からないのですが、エラーの原因はどこだと思われますか?
Microsoft Visual C++ 2010 Expressを使っています。
検証してみます。
ソースコードを書き換えたのであれば、新しいソースコードを提示してください。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

rarucchi
記事: 13
登録日時: 5年前

Re: C言語で最短経路探索プログラムを作っています。

#12

投稿記事 by rarucchi » 5年前

naohiro19 さんが書きました:rarucchiさんへ
Visual C++ 2010 Expressの 該当のソースコードを選択した状態で
「編集」→「詳細」→「ドキュメントのフォーマット」を選べば自動でソースコードを整えてくれますよ。
ありがとうございます、整えることができました。

rarucchi
記事: 13
登録日時: 5年前

Re: C言語で最短経路探索プログラムを作っています。

#13

投稿記事 by rarucchi » 5年前

新しいソースコードに更新しました
確認お願い致します。

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#14

投稿記事 by みけCAT » 5年前

最初のソースコードを書き換えるのではなく、新しい返信として新しいソースコードを投稿してもらえたほうがいいと思います。
説明も追記ではなく、新しい返信でお願いします。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

rarucchi
記事: 13
登録日時: 5年前

Re: C言語で最短経路探索プログラムを作っています。

#15

投稿記事 by rarucchi » 5年前

失礼しました。
変えた部分は、buffを1000に、88行目を0~nから1~nにしたことのみです。

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#16

投稿記事 by みけCAT » 5年前

nの値が読み込めずに0になっているため、mallocがうまく働かないのだと思います。
とりあえず、こちらの環境では*Nに1000を代入したらエラー無く結果が出力されました(正しい結果かは未検証です)。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef int errno_t;

errno_t fopen_s(FILE** fp, const char* filename, const char* mode) {
	if(*fp=fopen(filename,mode))return 0; else return 1;
}

char* strtok_s(char* buf,const char* delim,char** ptr) {
	return strtok(buf,delim);
}

#define OFF 0
#define ON 1

#define W(i,j) wght[n*(i)+(j)]

int *readweight(int *N,int *strt,int *dest) {
	int i,j,k,n,m,e;
	char *filename = "test.txt";
	FILE *fp;
	char buff[1000];
	int *wght;
	char* p;

	errno_t error;
	if((error = fopen_s(&fp,filename,"r")) !=0){
		printf("%s が開けません。\n",filename);exit(1);
	}
	// 総点数nを入力 //
	//fscanf(fp,"%d %d %d",&i,&j,&W(i,j)); グラフ生成班の読み込みの書き換えについて←を参考にしてはどうか
	//fscanf(fp,N="%p",&N);
	fgets(buff,1000,fp);
	*N = atoi(strtok_s(buff,"\n",&p));
	*N=1000; // ************************** テスト用 *****************************
	// 始点、終点を入力
	//fgets(buff,1000,fp);
	*strt = 1;
	*dest = 2;
	// 距離テーブル域確保、初期化
	n = *N;
	m = n*n;
	wght = (int *)malloc(m*sizeof(int));
	for(k=0;k<m;k++) wght[k] = INT_MAX;
	// 距離入力、テーブル格納
	fgets(buff,1000,fp);
	e = atoi(strtok_s(buff," \n", &p));
	while(fgets(buff,1000,fp)!=NULL) {
		i = atoi(strtok_s(buff," \n", &p));
		j = atoi(strtok_s(NULL," \n", &p));
		W(i,j) = atoi(strtok_s(NULL," \n", &p));
	}

	fclose(fp);
	return wght;
}

int main(void)
{
	int strt; // 出発点インデクス
	int dest; // 到着点インデクス
	int i; // 探索点インデクス
	int j; // 全走査インデクス
	int n; // 系の点の数
	int next; // 次の訪問先インデクス
	int dmin; // 次の訪問先への最少距離
	int *dist; // 始点からの最短距離
	int *vstd; // 訪問有無のフラグ
	int *prev; // 最短経路の先行点
	int *pass; // 最短経路遡行節点表
	int *wght; // 隣接点間距離
	int passable; // i-jの道がある
	int shortcut; // 既知の道より近い

	// 節点数を入力し、重み行列の場所取り
	// 最短経路始点終点の指定を入力
	// 重み行列を入力し、経路行列を作る
	wght = readweight(&n,&strt,&dest); // ←test.txt
	// アルゴリズム用、節点情報配列(4本)の場所取り
	dist = (int *)malloc(n*sizeof(int));
	vstd = (int *)malloc(n*sizeof(int));
	prev = (int *)malloc(n*sizeof(int));
	pass = (int *)malloc(n*sizeof(int));
	for(i=1;i<n;i++) { // vstd, dist の初期化
		vstd[i] = OFF; dist[i] = INT_MAX;
	}
	// アルゴリズム実現開始
	dist[strt] = 0; // 始点の始点からの距離=0
	prev[strt] = -1; // 始点の先行点はない(-1)
	next = strt; // 最初は始点を探索点とする
	do { // 未確認経路がなくなるまで繰り返す
		// 探索点iを設定する
		i = next; // 探索点 next を i とする
		vstd[i] = ON; // i の訪問フラグをオン
		dmin = INT_MAX; // 次の点への選択距離を最大化
		for(j=1;j<n;j++) { // i から次の点 j を探す
			if(vstd[j]) continue; // 点 j は決定済み
			// 未確定のjに到達する近道を選ぶ
			passable = W(i,j) < INT_MAX; // i→j移動可
			shortcut = dist[i] + W(i,j) < dist[j];
			// 点jへ通行可かつ既知の経路より近い?
			if(passable && shortcut) { // i→j を採用
				if(dist[i] != INT_MAX){
					dist[j] = dist[i]+W(i,j); // 最短距離更新
					prev[j] = i; // 点 j の先行点を i に変更
				}
			}
			// すべての到達可能なjから次の探索点を選ぶ
			if(dist[j] < dmin) {
				dmin = dist[j]; // 始点からの距離が最短
				next = j; // その j を次の探索点にする
			}
		}
	}while(dmin < INT_MAX);
	// 結果表示
	printf("総括表\n");
	printf("点 直前の点 最短距離\n");
	i=1;
	printf("%2d%10d%10d\n",i,i,dist[i]);
	for(i=1;i<n;i++) {
		if(i!=strt && vstd[i]) {
			printf("%2d%10d%10d\n",i,prev[i],dist[i]);
		}
	}
	printf("点%d-点%d 間の最適経路\n",strt,dest);
	i = dest; j=1; // i ← 終点
	while(i>=1) {
		pass[j++] = i; // pass 表 ← i
		i = prev[i]; // i ← 経路先行点
	} // 以上で経路の逆順に格納
	while(--j>=1) { // 逆順にたどる
		printf("%d",pass[j]); // 最短経路を表示
		if(j>1) printf("-");
		else printf("\n");
	}
	return 0;
}
出力

コード:

総括表
点 直前の点 最短距離
 1         1         0
 2         1         2
 3         1         4
15         1         4
22         1         2
24         1         7
31         1         4
32         1         1
45         1         2
47         1         1
53         1         5
58         1         4
65         1         8
75         1         7
79         1         9
80         1         7
81         1         6
91         1         1
95         1         9
96         1         2
102         1         3
点1-点2 間の最適経路
1-2
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#17

投稿記事 by みけCAT » 5年前

みけCAT さんが書きました:扱う辺のインデクスの操作がおかしいようです。
・0~(n-1)に統一し、読み込み時にiとjの値から1を引いてからW(i,j)に値を読み込む
・1~nに統一し、簡単のため各種領域はnを(n+1)としたときに必要な分を確保する
このどちらか一方を行うべきだと思います。
rarucchi さんが書きました:失礼しました。
変えた部分は、buffを1000に、88行目を0~nから1~nにしたことのみです。
ごめんなさい、定義不足でしたね。こう読み替えてください。

・[0,(n-1)]に統一し、読み込み時にiとjの値から1を引いてからW(i,j)に値を読み込む
・[1,n]に統一し、簡単のため各種領域はnを(n+1)としたときに必要な分を確保する

[a,b]は、閉区間(a以上b以下)を表します。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

rarucchi
記事: 13
登録日時: 5年前

Re: C言語で最短経路探索プログラムを作っています。

#18

投稿記事 by rarucchi » 5年前

私の環境でも実行することができました、ありがとうございます。

グラフの書式例として添付ファイルのような感じなのですが
辺の重みも考慮するためには何が足りないのでしょうか
添付ファイル
無題.png
無題.png (24.05 KiB) 閲覧数: 5717 回

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#19

投稿記事 by みけCAT » 5年前

rarucchi さんが書きました:グラフの書式例として添付ファイルのような感じなのですが
辺の重みも考慮するためには何が足りないのでしょうか
現状で辺の重みは考慮されていると思いますが、複数の辺をたどる経路に対応できていない感じです。
とりあえずいくつかのテストケースと、実行を楽にするバッチファイルを置いておきます。

run.bat (実行ファイル名はB4kadai.exeと仮定、第一引数に読み込ませたいテストケースのファイル名を指定する)

コード:

@echo off
if not "%1"=="test.txt" (
	move test.txt test_temp53463463.txt > NUL 2>&1
	move %1 test.txt > NUL 2>&1
)
B4kadai.exe
if not "%1"=="test.txt" (
	move test.txt %1 > NUL 2>&1
	move test_temp53463463.txt test.txt > NUL 2>&1
)
case1.txt

コード:

N=1000
E=2
1 1000 2
2 1000 3
case2.txt

コード:

N=1000
E=3
1 2 5
1 3 2
2 3 1
case3.txt

コード:

N=1000
E=2
1 3 5
2 3 3
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#20

投稿記事 by みけCAT » 5年前

割といい感じに動くように修正してみました。(本当に正しいかは未検証です)
元のグラフが無向グラフだとすると、データ上は両方向に辺を張るべきだと思います。
また、インデクス関連のバグを修正しました。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef int errno_t;

errno_t fopen_s(FILE** fp, const char* filename, const char* mode) {
	if(*fp=fopen(filename,mode))return 0; else return 1;
}

char* strtok_s(char* buf,const char* delim,char** ptr) {
	return strtok(buf,delim);
}

#define OFF 0
#define ON 1

#define W(i,j) wght[n*((i)-1)+(j)-1]

int *readweight(int *N,int *strt,int *dest) {
	int i,j,k,n,m,e;
	char *filename = "test.txt";
	FILE *fp;
	char buff[1000];
	int *wght;
	char* p;

	errno_t error;
	if((error = fopen_s(&fp,filename,"r")) !=0){
		printf("%s が開けません。\n",filename);exit(1);
	}
	// 総点数nを入力 //
	//fscanf(fp,"%d %d %d",&i,&j,&W(i,j)); グラフ生成班の読み込みの書き換えについて←を参考にしてはどうか
	//fscanf(fp,N="%p",&N);
	fgets(buff,1000,fp);
	*N = atoi(strtok_s(buff,"\n",&p)+2);
	// 始点、終点を入力
	//fgets(buff,1000,fp);
	*strt = 1;
	*dest = 2;
	// 距離テーブル域確保、初期化
	n = *N;
	m = n*n;
	wght = (int *)malloc(m*sizeof(int));
	for(k=0;k<m;k++) wght[k] = INT_MAX;
	// 距離入力、テーブル格納
	fgets(buff,1000,fp);
	e = atoi(strtok_s(buff," \n", &p)+2);
	while(fgets(buff,1000,fp)!=NULL) {
		i = atoi(strtok_s(buff," \n", &p));
		j = atoi(strtok_s(NULL," \n", &p));
		W(i,j) = W(j,i) = atoi(strtok_s(NULL," \n", &p));
	}

	fclose(fp);
	return wght;
}

int main(void)
{
	int strt; // 出発点インデクス
	int dest; // 到着点インデクス
	int i; // 探索点インデクス
	int j; // 全走査インデクス
	int n; // 系の点の数
	int next; // 次の訪問先インデクス
	int dmin; // 次の訪問先への最少距離
	int *dist; // 始点からの最短距離
	int *vstd; // 訪問有無のフラグ
	int *prev; // 最短経路の先行点
	int *pass; // 最短経路遡行節点表
	int *wght; // 隣接点間距離
	int passable; // i-jの道がある
	int shortcut; // 既知の道より近い

	// 節点数を入力し、重み行列の場所取り
	// 最短経路始点終点の指定を入力
	// 重み行列を入力し、経路行列を作る
	wght = readweight(&n,&strt,&dest); // ←test.txt
	// アルゴリズム用、節点情報配列(4本)の場所取り
	dist = (int *)malloc((n+1)*sizeof(int));
	vstd = (int *)malloc((n+1)*sizeof(int));
	prev = (int *)malloc((n+1)*sizeof(int));
	pass = (int *)malloc((n+1)*sizeof(int));
	for(i=1;i<=n;i++) { // vstd, dist の初期化
		vstd[i] = OFF; dist[i] = INT_MAX;
	}
	// アルゴリズム実現開始
	dist[strt] = 0; // 始点の始点からの距離=0
	prev[strt] = -1; // 始点の先行点はない(-1)
	next = strt; // 最初は始点を探索点とする
	do { // 未確認経路がなくなるまで繰り返す
		// 探索点iを設定する
		i = next; // 探索点 next を i とする
		vstd[i] = ON; // i の訪問フラグをオン
		dmin = INT_MAX; // 次の点への選択距離を最大化
		for(j=1;j<=n;j++) { // i から次の点 j を探す
			if(vstd[j]) continue; // 点 j は決定済み
			// 未確定のjに到達する近道を選ぶ
			passable = W(i,j) < INT_MAX; // i→j移動可
			shortcut = dist[i] + W(i,j) < dist[j];
			// 点jへ通行可かつ既知の経路より近い?
			if(passable && shortcut) { // i→j を採用
				if(dist[i] != INT_MAX){
					dist[j] = dist[i]+W(i,j); // 最短距離更新
					prev[j] = i; // 点 j の先行点を i に変更
				}
			}
			// すべての到達可能なjから次の探索点を選ぶ
			if(dist[j] < dmin) {
				dmin = dist[j]; // 始点からの距離が最短
				next = j; // その j を次の探索点にする
			}
		}
	}while(dmin < INT_MAX);
	// 結果表示
	printf("総括表\n");
	printf("点 直前の点 最短距離\n");
	i=1;
	printf("%2d%10d%10d\n",i,i,dist[i]);
	for(i=1;i<=n;i++) {
		if(i!=strt && vstd[i]) {
			printf("%2d%10d%10d\n",i,prev[i],dist[i]);
		}
	}
	printf("点%d-点%d 間の最適経路\n",strt,dest);
	i = dest; j=1; // i ← 終点
	while(i>=1) {
		pass[j++] = i; // pass 表 ← i
		i = prev[i]; // i ← 経路先行点
	} // 以上で経路の逆順に格納
	while(--j>=1) { // 逆順にたどる
		printf("%d",pass[j]); // 最短経路を表示
		if(j>1) printf("-");
		else printf("\n");
	}
	// 確保したメモリは開放しましょう
	free(wght);
	free(dist);
	free(vstd);
	free(prev);
	free(pass);
	return 0;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

rarucchi
記事: 13
登録日時: 5年前

Re: C言語で最短経路探索プログラムを作っています。

#21

投稿記事 by rarucchi » 5年前

申し訳ありません、バッチファイルについて調べたのですが初心者ゆえいまいち使い方を理解できませんでした。

最短経路の表示と一緒に、その最短経路の重みの合計も表示させてみようと思っているのですが可能でしょうか。

また、このソースプログラムについて計算時間をより速くする為に工夫すべき点などがあればアドバイス頂けると嬉しいです。

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#22

投稿記事 by みけCAT » 5年前

rarucchi さんが書きました:最短経路の表示と一緒に、その最短経路の重みの合計も表示させてみようと思っているのですが可能でしょうか。
はい。
単純に目的地の「最短距離」を表示すればいいと思います。
rarucchi さんが書きました:また、このソースプログラムについて計算時間をより速くする為に工夫すべき点などがあればアドバイス頂けると嬉しいです。
オーダーレベルで改善するなら、プライオリティーキューを使ったダイクストラ法に切り替える。
定数倍なら、例えば訪問していない頂点をリストで管理して、訪問したらリストから削除し、次回以降のループの回数を少なくする。
などの方法が考えられます。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

rarucchi
記事: 13
登録日時: 5年前

Re: C言語で最短経路探索プログラムを作っています。

#23

投稿記事 by rarucchi » 5年前

最短経路の距離ということはdist[j]を表示ですかね
みけCAT さんが書きました: 定数倍なら、例えば訪問していない頂点をリストで管理して、訪問したらリストから削除し、次回以降のループの回数を少なくする。
などの方法が考えられます。
是非詳しく教えてください。
課題自体は終了していますが、個人的に比較したいため計算時間を短縮したプログラムも実行したいです。

rarucchi
記事: 13
登録日時: 5年前

#24

投稿記事 by rarucchi » 5年前

また、プログラムの構造について理解が足りていないため

箇条書きのような形で大丈夫ですので、どのような流れで処理を行っているのか言葉で教えていただけると嬉しいです。

たいちう
記事: 418
登録日時: 8年前

Re: C言語で最短経路探索プログラムを作っています。

#25

投稿記事 by たいちう » 5年前

教えて、教えて、、、ではなく、
自分なりの学習や考察の過程をここに書き続けてくれると、
応援の意味を込めた誘導の書き込みが得られやすいのではないかと。

あなたのためにもなるし、過去ログを読む人のためにもなると思いますが。

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#26

投稿記事 by みけCAT » 5年前

rarucchi さんが書きました:箇条書きのような形で大丈夫ですので、どのような流れで処理を行っているのか言葉で教えていただけると嬉しいです。
すでに詳しいコメントがついていますが、不足でしょうか?
でしたら、CPUが「どのような流れで処理を行っているのか」をアセンブリ言語という「言葉」で記述したものを提示しておきます。
これはNo: 20のコードに相当します。
► スポイラーを表示
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#27

投稿記事 by みけCAT » 5年前

rarucchi さんが書きました:
みけCAT さんが書きました: 定数倍なら、例えば訪問していない頂点をリストで管理して、訪問したらリストから削除し、次回以降のループの回数を少なくする。
などの方法が考えられます。
是非詳しく教えてください。
課題自体は終了していますが、個人的に比較したいため計算時間を短縮したプログラムも実行したいです。
ごめんなさい。
実装してみましたが、逆に計算時間が延びてしまったようです。(添付のテストケースと手元の環境で、2.7秒程度→3.4秒程度)

【追記】
計算時間より結果を出力する時間の影響を強く受けていたようです。
結果の出力先を変更したら、それぞれ0.7秒程度、0.6秒程度で、このリストを利用するプログラムの方が速くなりました。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef int errno_t;

errno_t fopen_s(FILE** fp, const char* filename, const char* mode) {
	if(*fp=fopen(filename,mode))return 0; else return 1;
}

char* strtok_s(char* buf,const char* delim,char** ptr) {
	return strtok(buf,delim);
}

#define OFF 0
#define ON 1

#define W(i,j) wght[n*((i)-1)+(j)-1]

int *readweight(int *N,int *strt,int *dest) {
	int i,j,k,n,m,e;
	char *filename = "test.txt";
	FILE *fp;
	char buff[1000];
	int *wght;
	char* p;

	errno_t error;
	if((error = fopen_s(&fp,filename,"r")) !=0){
		printf("%s が開けません。\n",filename);exit(1);
	}
	// 総点数nを入力 //
	//fscanf(fp,"%d %d %d",&i,&j,&W(i,j)); グラフ生成班の読み込みの書き換えについて←を参考にしてはどうか
	//fscanf(fp,N="%p",&N);
	fgets(buff,1000,fp);
	*N = atoi(strtok_s(buff,"\n",&p)+2);
	// 始点、終点を入力
	//fgets(buff,1000,fp);
	*strt = 1;
	*dest = 2;
	// 距離テーブル域確保、初期化
	n = *N;
	m = n*n;
	wght = (int *)malloc(m*sizeof(int));
	for(k=0;k<m;k++) wght[k] = INT_MAX;
	// 距離入力、テーブル格納
	fgets(buff,1000,fp);
	e = atoi(strtok_s(buff," \n", &p)+2);
	while(fgets(buff,1000,fp)!=NULL) {
		i = atoi(strtok_s(buff," \n", &p));
		j = atoi(strtok_s(NULL," \n", &p));
		W(i,j) = W(j,i) = atoi(strtok_s(NULL," \n", &p));
	}

	fclose(fp);
	return wght;
}

int main(void)
{
	int strt; // 出発点インデクス
	int dest; // 到着点インデクス
	int i; // 探索点インデクス
	int j; // 全走査インデクス
	int n; // 系の点の数
	int next; // 次の訪問先インデクス
	int dmin; // 次の訪問先への最少距離
	int *next_search; // 次に探索するインデクス
	int *prev_search; // 前に探索するインデクス 
	int *dist; // 始点からの最短距離
	int *vstd; // 訪問有無のフラグ
	int *prev; // 最短経路の先行点
	int *pass; // 最短経路遡行節点表
	int *wght; // 隣接点間距離
	int passable; // i-jの道がある
	int shortcut; // 既知の道より近い

	// 節点数を入力し、重み行列の場所取り
	// 最短経路始点終点の指定を入力
	// 重み行列を入力し、経路行列を作る
	wght = readweight(&n,&strt,&dest); // ←test.txt
	// アルゴリズム用、節点情報配列(4本)の場所取り
	dist = (int *)malloc((n+1)*sizeof(int));
	vstd = (int *)malloc((n+1)*sizeof(int));
	prev = (int *)malloc((n+1)*sizeof(int));
	pass = (int *)malloc((n+1)*sizeof(int));
	// アルゴリズム用、リスト情報配列(2本)の場所取り
	next_search = (int *)malloc((n+2)*sizeof(int));
	prev_search = (int *)malloc((n+2)*sizeof(int));
	// ちゃんと場所が取れたかチェック
	if(wght==NULL || dist==NULL || vstd==NULL || prev==NULL || pass==NULL ||
	next_search==NULL || prev_search==NULL) {
		// 確保できていたメモリを開放
		if(wght)free(wght);
		if(dist)free(dist);
		if(vstd)free(vstd);
		if(prev)free(prev);
		if(pass)free(pass);
		if(next_search)free(next_search);
		if(prev_search)free(prev_search);
		// 終了
		printf("メモリ確保エラー\n");
		return 1;
	}
	for(i=1;i<=n;i++) { // vstd, dist の初期化
		vstd[i] = OFF; dist[i] = INT_MAX;
	}
	for(i=0;i<=n+1;i++) { // next_search, prev_searchの初期化
		next_search[i] = i+1; prev_search[i] = i-1;
	}
	// アルゴリズム実現開始
	dist[strt] = 0; // 始点の始点からの距離=0
	prev[strt] = -1; // 始点の先行点はない(-1)
	next = strt; // 最初は始点を探索点とする
	do { // 未確認経路がなくなるまで繰り返す
		// 探索点iを設定する
		i = next; // 探索点 next を i とする
		vstd[i] = ON; // i の訪問フラグをオン
		// i をリストから削除する
		next_search[prev_search[i]] = next_search[i];
		prev_search[next_search[i]] = prev_search[i];
		dmin = INT_MAX; // 次の点への選択距離を最大化
		for(j=next_search[0];j<=n;j=next_search[j]) { // i から次の点 j を探す
			if(vstd[j]) continue; // 点 j は決定済み
			// 未確定のjに到達する近道を選ぶ
			passable = W(i,j) < INT_MAX; // i→j移動可
			shortcut = dist[i] + W(i,j) < dist[j];
			// 点jへ通行可かつ既知の経路より近い?
			if(passable && shortcut) { // i→j を採用
				if(dist[i] != INT_MAX){
					dist[j] = dist[i]+W(i,j); // 最短距離更新
					prev[j] = i; // 点 j の先行点を i に変更
				}
			}
			// すべての到達可能なjから次の探索点を選ぶ
			if(dist[j] < dmin) {
				dmin = dist[j]; // 始点からの距離が最短
				next = j; // その j を次の探索点にする
			}
		}
	}while(dmin < INT_MAX);
	// 結果表示
	printf("総括表\n");
	printf("点 直前の点 最短距離\n");
	i=1;
	printf("%2d%10d%10d\n",i,i,dist[i]);
	for(i=1;i<=n;i++) {
		if(i!=strt && vstd[i]) {
			printf("%2d%10d%10d\n",i,prev[i],dist[i]);
		}
	}
	printf("点%d-点%d 間の最適経路\n",strt,dest);
	i = dest; j=1; // i ← 終点
	while(i>=1) {
		pass[j++] = i; // pass 表 ← i
		i = prev[i]; // i ← 経路先行点
	} // 以上で経路の逆順に格納
	while(--j>=1) { // 逆順にたどる
		printf("%d",pass[j]); // 最短経路を表示
		if(j>1) printf("-");
		else printf("\n");
	}
	// 確保したメモリを開放
	free(wght);
	free(dist);
	free(vstd);
	free(prev);
	free(pass);
	free(next_search);
	free(prev_search);
	return 0;
}
添付ファイル
casegen.zip
テストケース・ジェネレータ
(368 バイト) ダウンロード数: 32 回
case10000.txt
テストケース
(143.33 KiB) ダウンロード数: 33 回
最後に編集したユーザー みけCAT on 2014年7月17日(木) 17:13 [ 編集 1 回目 ]
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#28

投稿記事 by みけCAT » 5年前

他の小手先の高速化の方法としては、OpenMPを使うものがあります。

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef int errno_t;

errno_t fopen_s(FILE** fp, const char* filename, const char* mode) {
	if(*fp=fopen(filename,mode))return 0; else return 1;
}

char* strtok_s(char* buf,const char* delim,char** ptr) {
	return strtok(buf,delim);
}

#define OFF 0
#define ON 1

#define W(i,j) wght[n*((i)-1)+(j)-1]

int *readweight(int *N,int *strt,int *dest) {
	int i,j,k,n,m,e;
	char *filename = "test.txt";
	FILE *fp;
	char buff[1000];
	int *wght;
	char* p;

	errno_t error;
	if((error = fopen_s(&fp,filename,"r")) !=0){
		printf("%s が開けません。\n",filename);exit(1);
	}
	// 総点数nを入力 //
	//fscanf(fp,"%d %d %d",&i,&j,&W(i,j)); グラフ生成班の読み込みの書き換えについて←を参考にしてはどうか
	//fscanf(fp,N="%p",&N);
	fgets(buff,1000,fp);
	*N = atoi(strtok_s(buff,"\n",&p)+2);
	// 始点、終点を入力
	//fgets(buff,1000,fp);
	*strt = 1;
	*dest = 2;
	// 距離テーブル域確保、初期化
	n = *N;
	m = n*n;
	wght = (int *)malloc(m*sizeof(int));
	for(k=0;k<m;k++) wght[k] = INT_MAX;
	// 距離入力、テーブル格納
	fgets(buff,1000,fp);
	e = atoi(strtok_s(buff," \n", &p)+2);
	while(fgets(buff,1000,fp)!=NULL) {
		i = atoi(strtok_s(buff," \n", &p));
		j = atoi(strtok_s(NULL," \n", &p));
		W(i,j) = W(j,i) = atoi(strtok_s(NULL," \n", &p));
	}

	fclose(fp);
	return wght;
}

int main(void)
{
	int strt; // 出発点インデクス
	int dest; // 到着点インデクス
	int i; // 探索点インデクス
	int j; // 全走査インデクス
	int n; // 系の点の数
	int next; // 次の訪問先インデクス
	int dmin; // 次の訪問先への最少距離
	int *dist; // 始点からの最短距離
	int *vstd; // 訪問有無のフラグ
	int *prev; // 最短経路の先行点
	int *pass; // 最短経路遡行節点表
	int *wght; // 隣接点間距離
	int passable; // i-jの道がある
	int shortcut; // 既知の道より近い

	// 節点数を入力し、重み行列の場所取り
	// 最短経路始点終点の指定を入力
	// 重み行列を入力し、経路行列を作る
	wght = readweight(&n,&strt,&dest); // ←test.txt
	// アルゴリズム用、節点情報配列(4本)の場所取り
	dist = (int *)malloc((n+1)*sizeof(int));
	vstd = (int *)malloc((n+1)*sizeof(int));
	prev = (int *)malloc((n+1)*sizeof(int));
	pass = (int *)malloc((n+1)*sizeof(int));
	#pragma omp parallel for
	for(i=1;i<=n;i++) { // vstd, dist の初期化
		vstd[i] = OFF; dist[i] = INT_MAX;
	}
	// アルゴリズム実現開始
	dist[strt] = 0; // 始点の始点からの距離=0
	prev[strt] = -1; // 始点の先行点はない(-1)
	next = strt; // 最初は始点を探索点とする
	do { // 未確認経路がなくなるまで繰り返す
		// 探索点iを設定する
		i = next; // 探索点 next を i とする
		vstd[i] = ON; // i の訪問フラグをオン
		dmin = INT_MAX; // 次の点への選択距離を最大化
		#pragma omp parallel for
		for(j=1;j<=n;j++) { // i から次の点 j を探す
			if(vstd[j]) continue; // 点 j は決定済み
			// 未確定のjに到達する近道を選ぶ
			passable = W(i,j) < INT_MAX; // i→j移動可
			shortcut = dist[i] + W(i,j) < dist[j];
			// 点jへ通行可かつ既知の経路より近い?
			if(passable && shortcut) { // i→j を採用
				if(dist[i] != INT_MAX){
					dist[j] = dist[i]+W(i,j); // 最短距離更新
					prev[j] = i; // 点 j の先行点を i に変更
				}
			}
			// すべての到達可能なjから次の探索点を選ぶ
			#pragma omp flush(dmin)
			if(dist[j] < dmin) {
				#pragma omp critical
				{
					if(dist[j] < dmin) {
						dmin = dist[j]; // 始点からの距離が最短
						next = j; // その j を次の探索点にする
					}
				}
			}
		}
	}while(dmin < INT_MAX);
	// 結果表示
	printf("総括表\n");
	printf("点 直前の点 最短距離\n");
	i=1;
	printf("%2d%10d%10d\n",i,i,dist[i]);
	for(i=1;i<=n;i++) {
		if(i!=strt && vstd[i]) {
			printf("%2d%10d%10d\n",i,prev[i],dist[i]);
		}
	}
	printf("点%d-点%d 間の最適経路\n",strt,dest);
	i = dest; j=1; // i ← 終点
	while(i>=1) {
		pass[j++] = i; // pass 表 ← i
		i = prev[i]; // i ← 経路先行点
	} // 以上で経路の逆順に格納
	while(--j>=1) { // 逆順にたどる
		printf("%d",pass[j]); // 最短経路を表示
		if(j>1) printf("-");
		else printf("\n");
	}
	// 確保したメモリは開放しましょう
	free(wght);
	free(dist);
	free(vstd);
	free(prev);
	free(pass);
	return 0;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#29

投稿記事 by みけCAT » 5年前

申し訳ありません。
現状のプログラムは多重辺に対応していないのに、
さっき掲載したテストケース・ジェネレータは多重辺を生成する可能性があるという不都合がありました。
後ほど修正しようと思います。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6186
登録日時: 8年前
住所: 千葉県
連絡を取る:

Re: C言語で最短経路探索プログラムを作っています。

#30

投稿記事 by みけCAT » 5年前

再び申し訳ありません。
OpenMPを利用したプログラムにもまずい場所があるので、
後ほど修正版を投稿します。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

閉鎖

“C言語何でも質問掲示板” へ戻る