プログラムについて質問です。
プログラム初心者なのですが最短経路を探すプログラムを書きました。実行もできるのですが時間がかなりかかるので時間を短縮したいのですがどうすればいいでしょうか。環境はvisualC++2008を使ってます。
#include<stdio.h>
#include<limits.h>
#include<stdlib.h>
#include<time.h>
#define N 1000
#define E 3998
int e[N+1][N+1];
int w[N+1][N+1];
int s, sink;
int minLen;//始点sからどの点に移るか決める
int j;
int m;
int u[N+1];//距離
int f[N+1]={0};
int prev[N+1];//通ったノード
int start = 1;
int goal = 4;
void tansaku(int start)
{
for ( j=0 ; j<=N ; j++ ){
u[j] = 1000;
}
//始点s=0とする
s = start;
f[s] = 1;
u[s] = 0;
for( m=1 ; m<=N ; m++ ){
printf("現在位置[%d]\n", s);
//点sは最短経路決定
for( j=1 ; j<=N ; j++ ){
printf("e[%d][%d]=%d \nw[%d][%d]=%d\n\n", s, j, e[s][j], s, j, w[s][j]);
if( e[s][j] != 1 ){
//printf("[%d]には繋がってない\n", j);
//printf("-----------------------------------------\n");
continue; //枝(s,j)が存在しなければ以下の処理をスキップする
}
printf("[%d]に繋がってる→", j);
if( u[s]+w[s][j] < u[j] ){
printf("重み更新!\n");
u[j]=u[s]+w[s][j];
prev[j]=s; //点jへの経路長を更新、最短経路規定の点は除外
printf("u[%d] = %d\n", j, u[j]);
printf("prev[%d] = %d\n", j, prev[j]);
}else{
printf("重み更新なし...\n");
}
printf("-----------------------------------------\n");
}
/***************** 点sからどの点に移るか決める工程*******************/
minLen = 1000;
for( j=1 ; j<=N ; j++ ){
if( f[j] == 1 ){
printf("%dは通過済み\n", j);
continue;
}
printf("u[%d] = %d\n", j, u[j]);
if( u[j] < minLen ){
//点sは経路長が最短
minLen = u[j];
f[j] = 1;
s = j;
}
//ヒープを使う
}
if(s == goal){
printf("到着！！！！！\n");
minLen = 0;
printf("[経路]:");
while(s != start){
printf("%d ←", s);
s = prev[s];
}
printf("%d\n距離＝%d\n", start, u[goal]);
exit(1);
}
printf("次は%dです。\n", s);
}
printf("%d\n", prev[N]);
}
int main(void)
{
FILE *fp;
fopen_s(&fp, "text2.txt","r");
while ((fscanf_s(fp, "%d %d %d", &s, &j, &minLen)) != EOF){
printf("read\n");
e[s][j] = 1; //以下は１→２と２→１を同一に見なす
w[s][j] = minLen;
e[j][s] = 1;
w[j][s] = minLen;
}
fclose(fp);
tansaku(1);
return 0;
}
補足
回答ありがとうございました。 省略部分が多くてすみません。 ただ、最適化のレベルを低くすると正しい値となるので、プログラムそのものには問題がないと思います。 アセンブラの確認まではしませんでしたが、変数の前にvolatileをつけたら誤差が大きいもののほぼ正しい値となりました。 根本的な解決とはなりませんでしたが、最適化回避の方向で進めようと思います。