0

以下は、ダイクストラの最短パス アルゴリズムのコードです。このコードは小さな入力では問題なく動作しますが、2 次元配列のサイズが 200 の場合に必要です。そのため、動的メモリ割り当てを使用しました。それでも、null ポインターの割り当てエラーが発生します。大きなサイズの2次元配列を読み取る別の方法を見つけるのを手伝ってくれる人はいますか?

#include<stdio.h>
#include<conio.h>
#include<string.h>


void dij(int n,int v,int **c,int *d)
{
    int i,u,count,w,f[300];
    int min;

    for(i=1;i<=n;i++)
    {
        f[i]=0;d[i]=c[v][i];
    }

    f[v]=1,d[v]=1;

    count=2;

    while(count<=n)
    {
        min=1000000;
        for(w=1;w<=n;w++)
            if((d[w]<min)&&!f[w])
            {
                min=d[w];u=w;
            }
        f[u]=1;
        count++;

        for(w=1;w<=n;w++)
            if(((d[u]+c[u][w])<d[w])&&!f[w])
                d[w]=d[u]+c[u][w];
    }

}


int main()
{
    int v=1,n=4,i,j,k,len;
    char str[20];
    int **c,*d,val;

    d=(int*)malloc(n*sizeof(int));
    c=(int**)malloc(n*sizeof(int*));
    for(i=1;i<=n;i++)
        c[i]=(int*)malloc(n*sizeof(int));

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            c[i][j]=0;
    for(k=0;k<=n;k++)
    {
        do
        {
            scanf("%s",&str);
            len=strlen(str);
            if(len>3)
            {
                sscanf(str,"%d,%d",&j,&val);
                c[k][j]=val;
            }
            else break;
        }
        while(1);
    }

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            if(c[i][j]==0)
                c[i][j]=1000000;
        }

    printf("enter the source\n");

    scanf("%d",&v);

    dij(n,v,c,d);

    printf("shortest path from\n");

    for(i=1;i<=n;i++)
        if(i!=v)
            printf("%d -> %d=%d\n",v,i,d[i]);
    getch();
}
4

2 に答える 2

2 
for(i=1;i<=n;i++)

配列インデックスはゼロから始まります。

于 2012-07-20T17:24:09.253 に答える
0

f は [300] ですが、298 299 300 301 と 302 は試しましたか? すべて同じですか、それとも 300,301,302 がエラーですか?

関数 dij() では、i の最大値は n です。n を 300 より大きく設定すると、エラーが発生します

 int i,u,count,w,f[300];  // f[300]<---------constant size
 int min;


  for(i=1;i<=n;i++)

  {
     f[i]=0;d[i]=c[v][i];// here i goes to n, while f[] is f[300]

   }
于 2012-07-20T17:27:04.340 に答える