找最短路徑 Dijstra

發文回覆瀏覽次數：1326

推到 Plurk!

推到 Facebook!

尚未結案

linex2100
一般會員

發表：5
回覆：1
積分：1
註冊：2008-03-13

發送簡訊給我

#1 引用回覆回覆

發表時間：2008-04-09 00:32:04

IP:218.168.xxx.xxx 訂閱

我做成這樣可以印出起點到每個點的最短路徑長度

可是要印出路徑會有錯
例如說路徑是0 1 2 3 4
他只會印出 0 3 4
中間走過的1 2 就不會印出來
希望有高手能幫個忙

[code cpp]
#include
#include
#include

int main(){
int p=10,i,j,dis[p],near[p],flag[p],start=0,index,min;
int adv[10][10]={

{0, 9, 0, 0, 2, 9,0, 0, 0, 0},
{9, 0 ,5 ,0 ,6, 1 ,2, 0 ,0 ,0},
{0 ,5 ,0 ,3 ,0 ,0 ,1 ,1 ,0, 0 },
{0 ,0 ,3 ,0 ,0 ,0 ,2 ,3 ,0 ,0 },
{2 ,6 ,0 ,0 ,0 ,1 ,0 ,0 ,4 ,0 },
{9 ,1 ,0 ,0 ,1 ,0 ,3 ,0 ,1 ,0 },
{0 ,2 ,1 ,2 ,0 ,3 ,0 ,4 ,0 ,1 },
{0 ,0 ,1 ,3 ,0 ,0 ,4 ,0 ,0 ,2},
{0 ,0 ,0 ,0 ,4 ,1 ,0 ,0 ,0 ,1 },
{0 ,0, 0 ,0 ,0 ,0, 1 ,2, 1 ,0}

};

for(i=0;i for(j=0;j}

for(i=0;i if(adv[start][i]>0){
dis[i]=adv[start][i];
near[i]=start;
flag[i]=0;
}
else{
dis[i]=999;
near[i]=-1;
flag[i]=0;
}
}
dis[start]=0;
near[start]==-1;
flag[start]=1;

for(i=1;i for(j=0,min=999,index=-1;j if(flag[j]==0 && dis[j] min=dis[j];
index=j;
}
}
printf("選取%d\n",index);
if(index<0)break;
flag[index]=1;
for(j=0;j if(flag[j]==0 && adv[index][j]>0){
if((adv[index][j] dis[index]) printf("修正 %d\n",j);
dis[j]=adv[index][j] dis[index];
near[j]=index;
}
}
}
}

for(i=0;i if(near[start]=-1)
{
printf("%d ",start);
printf("%d %d 距離：%d\n",near[i],i,dis[i]);
if(i";
}

}

printf("\n");

system("pause");
}
[/code]

系統時間：2024-04-25 21:53:47

聯絡我們 | Delphi K.Top討論版

本站聲明

1. 本論壇為無營利行為之開放平台，所有文章都是由網友自行張貼，如牽涉到法律糾紛一切與本站無關。
2. 假如網友發表之內容涉及侵權，而損及您的利益，請立即通知版主刪除。
3. 請勿批評中華民國元首及政府或批評各政黨，是藍是綠本站無權干涉，但這裡不是政治性論壇！