void Dijkstra(AdjMatrix *G, int start, int end, int dist[], int path[][MAXVEX])
{
int mindist, i, j, k, t = 1;
for(i = 1; i <= G->vexnum; i++) {
dist[i] = G->arcs[start][i]; //對dist陣列初始化
if(G->arcs[start][i] != INFINITY)
path[i][1] = start;
}
path[start][0] = 1;
for(i = 2; i <= G->vexnum; i++) { //尋找各條最短路徑
mindist = INFINITY;
for(j = 1; j <= G->vexnum; j++)
if(!path[j][0] && dist[j] < mindist) {
k = j;
mindist = dist[j];
}
if(mindist == INFINITY)
return ;
path[k][0] = 1; //找到最短路徑
for(j = 1; j <= G->vexnum; j++) { //修改路徑
if(!path[j][0] && G->arcs[k][j] < INFINITY && dist[k]+G->arcs[k][j] < dist[j]) {
dist[j] = dist[k] + G->arcs[k][j];
t = 1;
while(path[k][t] != 0) {
path[j][t] = path[k][t];
t++;
}
path[j][t] = k;
path[j][t+1] = 0;
}
}
}
for(i = 1; i <= G->vexnum; i++)
if(i == end)
break;
printf("\n %s--->%s的最短路線為: 從%s",G->vex[start].name,G->vex[end].name,G->vex[start].name);
for(j = 2; path[i][j] != 0; j++) {
printf("->%s",G->vex[path[i][j]].name);
}
printf("->%s, 距離為%d m\n",G->vex[end].name,dist[i]);
printf("\n\t\t\t\t\t按任意鍵回傳...");
getch();
}
uj5u.com熱心網友回復：
你能不看代碼，描述清楚Dijkstra演算法是怎么作業的嗎如果能，代碼就能看
如果不能， 解釋也白費
這個要現有理論基礎的
uj5u.com熱心網友回復：
好的 我再仔細的理解下這個演算法uj5u.com熱心網友回復：
①情景描述②演算法簡介
③代碼實作
④測驗通過
uj5u.com熱心網友回復：
其實單源的我懂，這個我不太懂后面這塊
dist[j] = dist[k] + G->arcs[k][j];
t = 1;
while(path[k][t] != 0) {
path[j][t] = path[k][t];
t++;
}
path[j][t] = k;
path[j][t+1] = 0;
不知道t是干嘛的
uj5u.com熱心網友回復：
就是要實作輸入起點和終點，找最短路徑啊
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/124464.html
標籤：C語言
上一篇：求大神解答
下一篇：求解c語言檔案問題