作者FFFFFantasy (FFFFFantasy)
看板C_and_CPP
標題[問題] 不懂
時間Thu Jun 4 02:12:02 2009
main() {
int found[MAX_VERTICES];
int distance[MAX_VERTICES];
int cost[6][6]={0};
cost[0][1]=15;
cost[0][2]=10;
cost[1][3]=5;
cost[1][2]=20;
cost[2][4]=10;
cost[3][5]=15;
cost[4][5]=5;
for(int i=0;i<MAX_VERTICES;i++)
{
for(int j=0;j<MAX_VERTICES;j++)
cost[i][j]=cost[j][i];
}
shortestPath(0,&(*cost),&distance,6,&found);
cout<<"";
system("pause");
return 0;
}
void shortestPath(int v, int **cost,
int *distance, int n, short int
*found) //distance[i]代表頂點v到i的最短路徑
{ //found[i]=0表示路徑未找到,找到則為1
int i,u,w;
for(i=0; i<n; i++){
found[i]=0;
distance[i]=cost[v][i];
}
found[v]=1;
distance[v]=0;
for(i=0; i<n-2; i++){
u=choose(distance,n,found);
found[u]=1;
for(w=0; w<n; w++)
if(!found[w])
if(distance[u] + cost[u][w] < distance[w])
distance[w]=distance[w]+cost[u][w];
}
}
int choose(int distance[], int n, short int found[])
{ //找出還沒確認最短距離的點
int i, min, minpos;
min= I_MAX;
minpos = -1;
for(i=0; i<n; i++)
if(distance[i]<min && !found[i]){
min=distance[i];
minpos=i;
}
return minpos;
}
現在有個shortest path的問題，要找出最短路徑
可是不知道現在這個程式碼少了什麼
shortestPath(0,&(*cost),&distance,6,&found);←不知道裡面要放啥
cout<<"";
請大大幫忙
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.104.45
※ 編輯: FFFFFantasy 來自: 140.116.104.45 (06/04 02:24)
1F：→ azaz12345:這是Dijkstra演算法嗎 講清楚好解決@@ 06/04 13:24
2F：推 kinrall:對... 06/04 14:44