プログラムについて質問です。

質問

プログラム初心者なのですが最短経路を探すプログラムを書きました。実行もできるのですが時間がかなりかかるので時間を短縮したいのですがどうすればいいでしょうか。環境は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;
}

回答No.3

Tacosan

あぁ, #1 の意味がようやくわかった.

頂点が 3個しかないグラフでも無意味にループまわしてるのか....

回答No.2

Tacosan

とりあえず #1 でも言われているように「隣接しない点はチェックしない」ようにするくらいかなぁ.

本題じゃないけどこんなにグローバルな変数を無節操に使うプログラムもどうかと思う.

回答No.1

kmee

ごちゃごちゃしてて、流れはちゃんと追っていませんが。
とりあえず
「printfを極力減らす」
「ノードのあるものだけでループさえる」
というあたりではないでしょうか?