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

[rarucchi]

コード:

#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=１;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　というエラーが出てしまいます。

[みけCAT]

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

このコードなら、Eの値の保存は必要ないかもしれません。
グラフのINFとしてINT_MAXを用いると、オーバーフローしてやばいかもしれません。
【追記】
保護はしてあるようですね。
nの値を読み込む時に、先頭の"N="を読み飛ばす処理が必要だと思います。
【再追記】
dist[ i ]がINT_MAXのとき、そこに正の数W(i, j)を足すと、オーバーフローが発生します。
【さらに追記】
といっても、このプログラムでdist[ i ]がINT_MAXになることは無いかもしれません。

[みけCAT]

致命的ではなさそうですが、なぜreadweight関数でbuffをせっかく1000バイト確保しているのに、15バイトしか使わないのですか？

[みけCAT]

アルゴリズムとしては、おそらくO(N^2)版のダイクストラ法ですね。

[rarucchi]

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

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

[みけCAT]

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

無視する(読み飛ばす)ための文を入れる必要があります。

[みけCAT]

扱う辺のインデクスの操作がおかしいようです。
・0～(n-1)に統一し、読み込み時にiとjの値から1を引いてからW(i,j)に値を読み込む
・1～nに統一し、簡単のため各種領域はnを(n+1)としたときに必要な分を確保する
このどちらか一方を行うべきだと思います。

[rarucchi]

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

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

[rarucchi]

追記
実行したときに、
'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]

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

[みけCAT]

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

定義不足の気がするので、よくわかりません。

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

はい。

追記
実行したときに、

(中略)

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

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

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

検証してみます。
ソースコードを書き換えたのであれば、新しいソースコードを提示してください。

[rarucchi]

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

ありがとうございます、整えることができました。

[rarucchi]

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

[みけCAT]

最初のソースコードを書き換えるのではなく、新しい返信として新しいソースコードを投稿してもらえたほうがいいと思います。
説明も追記ではなく、新しい返信でお願いします。

[rarucchi]

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

[みけCAT]

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

[みけCAT]

扱う辺のインデクスの操作がおかしいようです。
・0～(n-1)に統一し、読み込み時にiとjの値から1を引いてからW(i,j)に値を読み込む
・1～nに統一し、簡単のため各種領域はnを(n+1)としたときに必要な分を確保する
このどちらか一方を行うべきだと思います。

失礼しました。
変えた部分は、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以下)を表します。

[rarucchi]

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

グラフの書式例として添付ファイルのような感じなのですが
辺の重みも考慮するためには何が足りないのでしょうか

[みけCAT]

グラフの書式例として添付ファイルのような感じなのですが
辺の重みも考慮するためには何が足りないのでしょうか

現状で辺の重みは考慮されていると思いますが、複数の辺をたどる経路に対応できていない感じです。
とりあえずいくつかのテストケースと、実行を楽にするバッチファイルを置いておきます。

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

[みけCAT]

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

コード:

#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;
}

[rarucchi]

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

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

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

[みけCAT]

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

はい。
単純に目的地の「最短距離」を表示すればいいと思います。

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

オーダーレベルで改善するなら、プライオリティーキューを使ったダイクストラ法に切り替える。
定数倍なら、例えば訪問していない頂点をリストで管理して、訪問したらリストから削除し、次回以降のループの回数を少なくする。
などの方法が考えられます。

[rarucchi]

最短経路の距離ということはdist[j]を表示ですかね

定数倍なら、例えば訪問していない頂点をリストで管理して、訪問したらリストから削除し、次回以降のループの回数を少なくする。
などの方法が考えられます。

是非詳しく教えてください。
課題自体は終了していますが、個人的に比較したいため計算時間を短縮したプログラムも実行したいです。

[rarucchi]

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

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

[たいちう]

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

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

[みけCAT]

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

すでに詳しいコメントがついていますが、不足でしょうか？
でしたら、CPUが「どのような流れで処理を行っているのか」をアセンブリ言語という「言葉」で記述したものを提示しておきます。
これはNo: 20のコードに相当します。

► スポイラーを表示

コード:

	.file	"c_saitan.c"
	.text
.globl _fopen_s
	.def	_fopen_s;	.scl	2;	.type	32;	.endef
_fopen_s:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$24, %esp
	movl	16(%ebp), %eax
	movl	%eax, 4(%esp)
	movl	12(%ebp), %eax
	movl	%eax, (%esp)
	call	_fopen
	movl	8(%ebp), %edx
	movl	%eax, (%edx)
	movl	8(%ebp), %eax
	movl	(%eax), %eax
	testl	%eax, %eax
	je	L2
	movl	$0, %eax
	jmp	L3
L2:
	movl	$1, %eax
L3:
	leave
	ret
.globl _strtok_s
	.def	_strtok_s;	.scl	2;	.type	32;	.endef
_strtok_s:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$24, %esp
	movl	12(%ebp), %eax
	movl	%eax, 4(%esp)
	movl	8(%ebp), %eax
	movl	%eax, (%esp)
	call	_strtok
	leave
	ret
	.section .rdata,"dr"
LC0:
	.ascii "test.txt\0"
LC1:
	.ascii "r\0"
LC2:
	.ascii "%s \202\252\212J\202\257\202\334\202\271\202\361\201B\12\0"
LC3:
	.ascii "\12\0"
LC4:
	.ascii " \12\0"
	.text
.globl _readweight
	.def	_readweight;	.scl	2;	.type	32;	.endef
_readweight:
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%esi
	pushl	%ebx
	subl	$1072, %esp
	movl	$LC0, -16(%ebp)
	movl	$LC1, 8(%esp)
	movl	-16(%ebp), %eax
	movl	%eax, 4(%esp)
	leal	-48(%ebp), %eax
	movl	%eax, (%esp)
	call	_fopen_s
	movl	%eax, -20(%ebp)
	cmpl	$0, -20(%ebp)
	je	L6
	movl	-16(%ebp), %eax
	movl	%eax, 4(%esp)
	movl	$LC2, (%esp)
	call	_printf
	movl	$1, (%esp)
	call	_exit
L6:
	movl	-48(%ebp), %eax
	movl	%eax, 8(%esp)
	movl	$1000, 4(%esp)
	leal	-1048(%ebp), %eax
	movl	%eax, (%esp)
	call	_fgets
	leal	-1052(%ebp), %eax
	movl	%eax, 8(%esp)
	movl	$LC3, 4(%esp)
	leal	-1048(%ebp), %eax
	movl	%eax, (%esp)
	call	_strtok_s
	addl	$2, %eax
	movl	%eax, (%esp)
	call	_atoi
	movl	8(%ebp), %edx
	movl	%eax, (%edx)
	movl	12(%ebp), %eax
	movl	$1, (%eax)
	movl	16(%ebp), %eax
	movl	$2, (%eax)
	movl	8(%ebp), %eax
	movl	(%eax), %eax
	movl	%eax, -24(%ebp)
	movl	-24(%ebp), %eax
	imull	-24(%ebp), %eax
	movl	%eax, -28(%ebp)
	movl	-28(%ebp), %eax
	sall	$2, %eax
	movl	%eax, (%esp)
	call	_malloc
	movl	%eax, -32(%ebp)
	movl	$0, -12(%ebp)
	jmp	L7
L8:
	movl	-12(%ebp), %eax
	sall	$2, %eax
	addl	-32(%ebp), %eax
	movl	$2147483647, (%eax)
	incl	-12(%ebp)
L7:
	movl	-12(%ebp), %eax
	cmpl	-28(%ebp), %eax
	jl	L8
	movl	-48(%ebp), %eax
	movl	%eax, 8(%esp)
	movl	$1000, 4(%esp)
	leal	-1048(%ebp), %eax
	movl	%eax, (%esp)
	call	_fgets
	leal	-1052(%ebp), %eax
	movl	%eax, 8(%esp)
	movl	$LC4, 4(%esp)
	leal	-1048(%ebp), %eax
	movl	%eax, (%esp)
	call	_strtok_s
	addl	$2, %eax
	movl	%eax, (%esp)
	call	_atoi
	movl	%eax, -36(%ebp)
	jmp	L9
L10:
	leal	-1052(%ebp), %eax
	movl	%eax, 8(%esp)
	movl	$LC4, 4(%esp)
	leal	-1048(%ebp), %eax
	movl	%eax, (%esp)
	call	_strtok_s
	movl	%eax, (%esp)
	call	_atoi
	movl	%eax, -40(%ebp)
	leal	-1052(%ebp), %eax
	movl	%eax, 8(%esp)
	movl	$LC4, 4(%esp)
	movl	$0, (%esp)
	call	_strtok_s
	movl	%eax, (%esp)
	call	_atoi
	movl	%eax, -44(%ebp)
	movl	-40(%ebp), %eax
	decl	%eax
	imull	-24(%ebp), %eax
	addl	-44(%ebp), %eax
	decl	%eax
	sall	$2, %eax
	movl	%eax, %esi
	addl	-32(%ebp), %esi
	movl	-44(%ebp), %eax
	decl	%eax
	imull	-24(%ebp), %eax
	addl	-40(%ebp), %eax
	decl	%eax
	sall	$2, %eax
	movl	%eax, %ebx
	addl	-32(%ebp), %ebx
	leal	-1052(%ebp), %eax
	movl	%eax, 8(%esp)
	movl	$LC4, 4(%esp)
	movl	$0, (%esp)
	call	_strtok_s
	movl	%eax, (%esp)
	call	_atoi
	movl	%eax, (%ebx)
	movl	(%ebx), %eax
	movl	%eax, (%esi)
L9:
	movl	-48(%ebp), %eax
	movl	%eax, 8(%esp)
	movl	$1000, 4(%esp)
	leal	-1048(%ebp), %eax
	movl	%eax, (%esp)
	call	_fgets
	testl	%eax, %eax
	jne	L10
	movl	-48(%ebp), %eax
	movl	%eax, (%esp)
	call	_fclose
	movl	-32(%ebp), %eax
	addl	$1072, %esp
	popl	%ebx
	popl	%esi
	leave
	ret
	.def	___main;	.scl	2;	.type	32;	.endef
	.section .rdata,"dr"
LC5:
	.ascii "\221\215\212\207\225\\\0"
LC6:
	.ascii "\223_ \222\274\221O\202\314\223_ \215\305\222Z\213\227\227\243\0"
LC7:
	.ascii "%2d%10d%10d\12\0"
LC8:
	.ascii "\223_%d-\223_%d \212\324\202\314\215\305\223K\214o\230H\12\0"
LC9:
	.ascii "%d\0"
	.text
.globl _main
	.def	_main;	.scl	2;	.type	32;	.endef
_main:
	pushl	%ebp
	movl	%esp, %ebp
	andl	$-16, %esp
	pushl	%ebx
	subl	$92, %esp
	call	___main
	leal	28(%esp), %eax
	movl	%eax, 8(%esp)
	leal	32(%esp), %eax
	movl	%eax, 4(%esp)
	leal	24(%esp), %eax
	movl	%eax, (%esp)
	call	_readweight
	movl	%eax, 60(%esp)
	movl	24(%esp), %eax
	incl	%eax
	sall	$2, %eax
	movl	%eax, (%esp)
	call	_malloc
	movl	%eax, 56(%esp)
	movl	24(%esp), %eax
	incl	%eax
	sall	$2, %eax
	movl	%eax, (%esp)
	call	_malloc
	movl	%eax, 52(%esp)
	movl	24(%esp), %eax
	incl	%eax
	sall	$2, %eax
	movl	%eax, (%esp)
	call	_malloc
	movl	%eax, 48(%esp)
	movl	24(%esp), %eax
	incl	%eax
	sall	$2, %eax
	movl	%eax, (%esp)
	call	_malloc
	movl	%eax, 44(%esp)
	movl	$1, 76(%esp)
	jmp	L12
L13:
	movl	76(%esp), %eax
	sall	$2, %eax
	addl	52(%esp), %eax
	movl	$0, (%eax)
	movl	76(%esp), %eax
	sall	$2, %eax
	addl	56(%esp), %eax
	movl	$2147483647, (%eax)
	incl	76(%esp)
L12:
	movl	24(%esp), %eax
	cmpl	%eax, 76(%esp)
	jle	L13
	movl	32(%esp), %eax
	sall	$2, %eax
	addl	56(%esp), %eax
	movl	$0, (%eax)
	movl	32(%esp), %eax
	sall	$2, %eax
	addl	48(%esp), %eax
	movl	$-1, (%eax)
	movl	32(%esp), %eax
	movl	%eax, 68(%esp)
L19:
	movl	68(%esp), %eax
	movl	%eax, 76(%esp)
	movl	76(%esp), %eax
	sall	$2, %eax
	addl	52(%esp), %eax
	movl	$1, (%eax)
	movl	$2147483647, 64(%esp)
	movl	$1, 72(%esp)
	jmp	L14
L18:
	movl	72(%esp), %eax
	sall	$2, %eax
	addl	52(%esp), %eax
	movl	(%eax), %eax
	testl	%eax, %eax
	jne	L28
L15:
	movl	76(%esp), %eax
	leal	-1(%eax), %edx
	movl	24(%esp), %eax
	imull	%edx, %eax
	addl	72(%esp), %eax
	decl	%eax
	sall	$2, %eax
	addl	60(%esp), %eax
	movl	(%eax), %eax
	cmpl	$2147483647, %eax
	setne	%al
	movzbl	%al, %eax
	movl	%eax, 40(%esp)
	movl	76(%esp), %eax
	sall	$2, %eax
	addl	56(%esp), %eax
	movl	(%eax), %edx
	movl	76(%esp), %eax
	leal	-1(%eax), %ecx
	movl	24(%esp), %eax
	imull	%ecx, %eax
	addl	72(%esp), %eax
	decl	%eax
	sall	$2, %eax
	addl	60(%esp), %eax
	movl	(%eax), %eax
	addl	%eax, %edx
	movl	72(%esp), %eax
	sall	$2, %eax
	addl	56(%esp), %eax
	movl	(%eax), %eax
	cmpl	%eax, %edx
	setl	%al
	movzbl	%al, %eax
	movl	%eax, 36(%esp)
	cmpl	$0, 40(%esp)
	je	L17
	cmpl	$0, 36(%esp)
	je	L17
	movl	76(%esp), %eax
	sall	$2, %eax
	addl	56(%esp), %eax
	movl	(%eax), %eax
	cmpl	$2147483647, %eax
	je	L17
	movl	72(%esp), %eax
	sall	$2, %eax
	addl	56(%esp), %eax
	movl	76(%esp), %edx
	sall	$2, %edx
	addl	56(%esp), %edx
	movl	(%edx), %ecx
	movl	76(%esp), %edx
	leal	-1(%edx), %ebx
	movl	24(%esp), %edx
	imull	%ebx, %edx
	addl	72(%esp), %edx
	decl	%edx
	sall	$2, %edx
	addl	60(%esp), %edx
	movl	(%edx), %edx
	leal	(%ecx,%edx), %edx
	movl	%edx, (%eax)
	movl	72(%esp), %eax
	sall	$2, %eax
	addl	48(%esp), %eax
	movl	76(%esp), %edx
	movl	%edx, (%eax)
L17:
	movl	72(%esp), %eax
	sall	$2, %eax
	addl	56(%esp), %eax
	movl	(%eax), %eax
	cmpl	64(%esp), %eax
	jge	L16
	movl	72(%esp), %eax
	sall	$2, %eax
	addl	56(%esp), %eax
	movl	(%eax), %eax
	movl	%eax, 64(%esp)
	movl	72(%esp), %eax
	movl	%eax, 68(%esp)
	jmp	L16
L28:
	nop
L16:
	incl	72(%esp)
L14:
	movl	24(%esp), %eax
	cmpl	%eax, 72(%esp)
	jle	L18
	cmpl	$2147483647, 64(%esp)
	jne	L19
	movl	$LC5, (%esp)
	call	_puts
	movl	$LC6, (%esp)
	call	_puts
	movl	$1, 76(%esp)
	movl	76(%esp), %eax
	sall	$2, %eax
	addl	56(%esp), %eax
	movl	(%eax), %eax
	movl	%eax, 12(%esp)
	movl	76(%esp), %eax
	movl	%eax, 8(%esp)
	movl	76(%esp), %eax
	movl	%eax, 4(%esp)
	movl	$LC7, (%esp)
	call	_printf
	movl	$1, 76(%esp)
	jmp	L20
L22:
	movl	32(%esp), %eax
	cmpl	%eax, 76(%esp)
	je	L21
	movl	76(%esp), %eax
	sall	$2, %eax
	addl	52(%esp), %eax
	movl	(%eax), %eax
	testl	%eax, %eax
	je	L21
	movl	76(%esp), %eax
	sall	$2, %eax
	addl	56(%esp), %eax
	movl	(%eax), %edx
	movl	76(%esp), %eax
	sall	$2, %eax
	addl	48(%esp), %eax
	movl	(%eax), %eax
	movl	%edx, 12(%esp)
	movl	%eax, 8(%esp)
	movl	76(%esp), %eax
	movl	%eax, 4(%esp)
	movl	$LC7, (%esp)
	call	_printf
L21:
	incl	76(%esp)
L20:
	movl	24(%esp), %eax
	cmpl	%eax, 76(%esp)
	jle	L22
	movl	28(%esp), %edx
	movl	32(%esp), %eax
	movl	%edx, 8(%esp)
	movl	%eax, 4(%esp)
	movl	$LC8, (%esp)
	call	_printf
	movl	28(%esp), %eax
	movl	%eax, 76(%esp)
	movl	$1, 72(%esp)
	jmp	L23
L24:
	movl	72(%esp), %eax
	sall	$2, %eax
	addl	44(%esp), %eax
	movl	76(%esp), %edx
	movl	%edx, (%eax)
	incl	72(%esp)
	movl	76(%esp), %eax
	sall	$2, %eax
	addl	48(%esp), %eax
	movl	(%eax), %eax
	movl	%eax, 76(%esp)
L23:
	cmpl	$0, 76(%esp)
	jg	L24
	jmp	L25
L27:
	movl	72(%esp), %eax
	sall	$2, %eax
	addl	44(%esp), %eax
	movl	(%eax), %eax
	movl	%eax, 4(%esp)
	movl	$LC9, (%esp)
	call	_printf
	cmpl	$1, 72(%esp)
	jle	L26
	movl	$45, (%esp)
	call	_putchar
	jmp	L25
L26:
	movl	$10, (%esp)
	call	_putchar
L25:
	decl	72(%esp)
	cmpl	$0, 72(%esp)
	jg	L27
	movl	60(%esp), %eax
	movl	%eax, (%esp)
	call	_free
	movl	56(%esp), %eax
	movl	%eax, (%esp)
	call	_free
	movl	52(%esp), %eax
	movl	%eax, (%esp)
	call	_free
	movl	48(%esp), %eax
	movl	%eax, (%esp)
	call	_free
	movl	44(%esp), %eax
	movl	%eax, (%esp)
	call	_free
	movl	$0, %eax
	addl	$92, %esp
	popl	%ebx
	leave
	ret
	.def	_fopen;	.scl	2;	.type	32;	.endef
	.def	_strtok;	.scl	2;	.type	32;	.endef
	.def	_printf;	.scl	2;	.type	32;	.endef
	.def	_exit;	.scl	2;	.type	32;	.endef
	.def	_fgets;	.scl	2;	.type	32;	.endef
	.def	_atoi;	.scl	2;	.type	32;	.endef
	.def	_malloc;	.scl	2;	.type	32;	.endef
	.def	_fclose;	.scl	2;	.type	32;	.endef
	.def	_puts;	.scl	2;	.type	32;	.endef
	.def	_putchar;	.scl	2;	.type	32;	.endef
	.def	_free;	.scl	2;	.type	32;	.endef

[みけ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;
}

[みけCAT]

他の小手先の高速化の方法としては、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;
}

[みけCAT]

申し訳ありません。
現状のプログラムは多重辺に対応していないのに、
さっき掲載したテストケース・ジェネレータは多重辺を生成する可能性があるという不都合がありました。
後ほど修正しようと思います。

[みけCAT]

再び申し訳ありません。
OpenMPを利用したプログラムにもまずい場所があるので、
後ほど修正版を投稿します。

[みけCAT]

OpenMPを使ったプログラムを修正しましたが、
やはり出力の影響が大きかったようで、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) {
		int weight;
		i = atoi(strtok_s(buff," \n", &p));
		j = atoi(strtok_s(NULL," \n", &p));
		weight = atoi(strtok_s(NULL," \n", &p));
		if(W(i,j)>weight) W(i,j) = weight;
		if(W(j,i)>weight) W(j,i) = weight;
	}

	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; // 隣接点間距離

	// 節点数を入力し、重み行列の場所取り
	// 最短経路始点終点の指定を入力
	// 重み行列を入力し、経路行列を作る
	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));
	#ifdef _OPENMP
	#pragma omp parallel for
	#endif
	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; // 最初は始点を探索点とする
	#ifdef _OPENMP
	#pragma omp parallel
	{
	#endif
	do { // 未確認経路がなくなるまで繰り返す
		// 探索点iを設定する
		#ifdef _OPENMP
		#pragma omp barrier
		#pragma omp single
		{
		#endif
		i = next; // 探索点 next を i とする
		vstd[i] = ON; // i の訪問フラグをオン
		dmin = INT_MAX; // 次の点への選択距離を最大化
		#ifdef _OPENMP
		}
		#pragma omp for
		#endif
		for(j=1;j<=n;j++) { // i から次の点 j を探す
			int passable; // i-jの道がある
			int shortcut; // 既知の道より近い

			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から次の探索点を選ぶ
			#ifdef _OPENMP
			#pragma omp flush(dmin)
			if(dist[j] < dmin) {
				#pragma omp critical
				{
			#endif
					if(dist[j] < dmin) {
						dmin = dist[j]; // 始点からの距離が最短
						next = j; // その j を次の探索点にする
					}
			#ifdef _OPENMP
				}
			}
			#endif
		}
		#ifdef _OPENMP
		#pragma omp flush(dmin,next)
		#endif
	}while(dmin < INT_MAX);
	#ifdef _OPENMP
	#pragma omp barrier
	}
	#endif
	// 結果表示
	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;
}

また、修正版のテストケース・ジェネレータを添付します。

次の定数倍高速化の方法としては、現行の隣接行列をつかったグラフの表現を、各頂点にそこから出ている辺の集合を持たせる表現にすることが考えられます。
これにより、辺が出ていない頂点をいちいちチェックする必要がなくなります。

[rarucchi]

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

このプログラムが自分の体感ですが、1秒弱程速い感じがしました。
グラフの表現の仕方について考えてみようと思います。

ついでに現在、最短経路の距離の表示を、
printf("%d",dist[dest]);
と記述しているのですがこれで正しいでしょうか。

[みけCAT]

ついでに現在、最短経路の距離の表示を、
printf("%d",dist[dest]);
と記述しているのですがこれで正しいでしょうか。

はい、大丈夫だと思います。

[rarucchi]

next_search[prev_search] = next_search;
prev_search[next_search] = prev_search;

ここで訪問した頂点をリストから削除するという作業が行っているのですか？

[みけCAT]

next_search[prev_search] = next_search;
prev_search[next_search] = prev_search;

ここで訪問した頂点をリストから削除するという作業が行っているのですか？

はい。