1 const int MAXINT = 32767; 2 const int MAXNUM = 10; //點的個數(shù) 3 int dist[MAXNUM]; 4 int prev[MAXNUM]; 5 6 int A[MAXUNM][MAXNUM]; 7 8 void Dijkstra(int v0) 9 { 10 　　bool S[MAXNUM]; // 新建一個標(biāo)記數(shù)組，判斷是否已存入該點到S集合中； 11 int n=MAXNUM; 12 　　for(int i=1; i<=n; ++i) 13 　　 { 14 　　dist[i] = A[v0][i]; //將該點的鄰接矩陣復(fù)制到dist[]一維數(shù)組中； 15 　　S[i] = false; // 初始都未用過該點； 16 　　if(dist[i] == MAXINT) 17 　　prev[i] = -1; 18 　　 else 19 　　prev[i] = v0; //記錄該點的上一節(jié)點是現(xiàn)在處理的源點，如果不聯(lián)通為-1； 20 　　} 21 　 dist[v0] = 0; //dist表示原點v0到該點的最短距離； 22 　 S[v0] = true; 　　 //將源點標(biāo)記為已經(jīng)訪問； 23 　　 for(int i=2; i<=n; i++) //循環(huán)n-1次，保證找到每一個點； 24 　　 { 25 　　int mindist = MAXINT; //標(biāo)記當(dāng)前的最小距離，初始化為最大； 26 　　int u = v0; 　　 // 找出當(dāng)前未使用的點j的dist[j]最小值 27 　　 for(int j=1; j<=n; ++j) 28 　　 if((!S[j]) && dist[j]<mindist) 29 　　 { 30 　　 u = j; // u保存當(dāng)前鄰接點中距離最小的點的號碼 31 　 　 mindist = dist[j]; 32 　　 } //找出了距離該源點最近的那個點，u記錄了點的編號； 33 　　S[u] = true; 34 　　for(int j=1; j<=n; j++) 35 　　 if((!S[j]) && A[u][j]<MAXINT) //找沒有被使用過的點，且與u是聯(lián)通的點； 36 　　 { 37 　 　if(dist[u] + A[u][j] < dist[j]) //在通過新加入的u點路徑找到離v0點更短的路徑 ；（如果該點距離原點的距離比從u點過度過來的距離長，則當(dāng)前的最短路就改變） 38 　 　{ 39 　　dist[j] = dist[u] + A[u][j]; //更新dist 40 　　prev[j] = u; //記錄前驅(qū)頂點 41 　　 } 42 　 　} 43 　　} 44 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/by-1075324834/p/4388919.html

總結(jié)

以上是生活随笔為你收集整理的最短路---dijsktra--邻接矩阵的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。