|
こんばんわ。
最短経路の求解プログラムを作ってみたのですが、
下記のような感じになっています。
このままならいいのですが、データ数を増やして計算したいので、
具体的にいうと、define N 100となっている所を600とかもっと大きいデータ
数にしたいのですが、このままの2次元配列を作ると36万個も･…
メモリが･…
といった感じになっています。
読み込みたいデータは、頂点の数は多いものの、
枝の数はたいしてありません。
うまい方法は、無いでしょうか
読み込んでるファイルは、
頂点数 枝の数
頂点番号1 頂点番号2 距離
頂点番号1 頂点番号3 距離
・
・
といった書式になっています。
#include <stdio.h>
#define N 100
void main(void)
{
int i,j;
int n,m,vi,vj,wij,vs,vt,min,marknum;
int adj[N+1][N+1],mark[N+1],length[N+1],pred[N+1];
FILE *fp;
fp=fopen("spath3goudata", "r");
fscanf(fp,"%d%d",&n,&m);
for(i=1;i<=n;i++)
{
mark[i]=0; length[i]=999;
for(j=1;j<=n;j++)adj[i][j]=999;
}
for(i=1;i<=m;i++)
{
fscanf(fp,"%d%d%d",&vi,&vj,&wij);
adj[vi][vj]=adj[vj][vi]=wij;
}
printf("siten =");
scanf("%d",&vs);
printf("syuuten =");
scanf("%d",&vt);
length[vs]=0;
marknum=0;
while(marknum<n)
{
min=999;
for(i=1;i<=n;i++)
{
if(mark[i]==0&&min>=length[i])
{
min=length[i]; vi=i;
}
}
mark[vi]=1;marknum++;
for(vj=1;vj<=n;vj++)
{
if(adj[vi][vj]!=999 && mark[vj]!=1)
{
if(length[vj]>(length[vi]+adj[vi][vj]))
{
length[vj]=length[vi]+adj[vi][vj];
pred[vj]=vi;
}
}
}
}
i=vt;
while(i!=vs){
printf("->%d",pred[i]);
i=pred[i];
}
}
|
