最短路徑之Dijkstra算法 C語言實現(xiàn)
轉載鏈接：https://blog.csdn.net/qq_34845121/article/details/62056089
姓名：羅學元學號：21181214375 ????學院：廣州研究院
【嵌牛導讀】最短路徑之Dijkstra算法 C語言實現(xiàn)
【嵌牛鼻子】最短路徑之Dijkstra算法 C語言實現(xiàn)
【嵌牛提問】最短路徑之Dijkstra算法 C語言如何實現(xiàn)
Dijkstra算法（單源點路徑算法，要求：圖中不存在負權值邊）：
步驟：a. ?初始時，S只包含源點，即S＝{v}，v的距離為0。U包含除v外的其他頂點，即: U={其余頂點}，若v與U中頂點u有邊，則u的距離設置為相應的權值，若u v之間不存在邊，則 ? ? ? ?設置u的距離為無窮大。b. ?從U中選取一個距離 v 最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。c. 以k為新考慮的中間點，修改U中各頂點的距離；若從源點 v 到頂點 u 的距離（經過頂點 k）比原來距離（不經過頂點 k）短，則修改頂點u的距離值，修改后的距離值為頂點 k 的距離加上邊<k v>的權值。
d. 重復步驟b和c直到所有頂點都包含在S中。
代碼在此:
#include<stdio.h>
#define SIZE 110 ?
#define INF 1000000; ?
int map[SIZE][SIZE]; ?//鄰接矩陣存儲
int len[SIZE]; ? //d[i]表示源點到i這個點的距離
int visit[SIZE]; ?//節(jié)點是否被訪問
int n,m; ?
int dijkstra(int from, int to){ //從源點到目標點
????int i; ?
????for(i = 1 ; i <= n ; i ++){ //初始化
????????visit[i] = 0; //一開始每個點都沒被訪問
????????len[i] = map[from][i]; //先假設源點到其他點的距離
????} ?
????int j; ?
????for(i = 1 ; i < n ; ++i){ //對除源點的每一個點進行最短計算
int min = INF; ?//記錄最小len[i]
int pos; ?//記錄小len[i] 的點
????????for(j = 1 ; j <= n ; ++j){
????????????if(!visit[j] && min > len[j]){ ?
????????????????pos = j; ?
????????????????min = len[j]; ?
????????????} ?
????????} ?
????????visit[pos] = 1; ?
????????for(j = 1 ; j <= n ; ++j){
if(!visit[j] && (len[j] > (len[pos] +map[pos][j]))){ //如果j節(jié)點沒有被訪問過&&j節(jié)點到源節(jié)點的最短路徑>pos節(jié)點到源節(jié)點的最短路徑+pos節(jié)點到j節(jié)點的路徑 ?
????????????????len[j] = len[pos] + map[pos][j]; //更新j節(jié)點到源節(jié)點的最短路徑
????????????} ?
????????} ?
????} ?
????return len[to];
}
int main () { ?
????int i,j; ?
??// ?scanf("%d%d",&n,&m); //輸入數(shù)據(jù)
n = 6; //測試數(shù)據(jù)
m = 9;
????for(i = 1 ; i <= n ; ++i){ //設一開始每個點都不可達
????????for(j = 1 ; j <= n ; ++j){ ?
????????????map[i][j] = INF; ?
????????} ?
????} ?
/* int a,b,c; //輸入數(shù)據(jù)
????for(i = 1 ; i <= m ; ++i){ ?
????????scanf("%d%d%d",&a,&b,&c); ?
????????map[a][b] = map[b][a] = c; ?
????} ?*/
????map[1][2] = 7; //測試數(shù)據(jù)
map[1][3] = 9;
map[1][6] = 14;
map[2][3] = 10;
map[2][4] = 15;
map[3][6] = 2;
map[5][6] = 9;
map[4][5] = 6;
map[3][4] = 11;
????int temp = INF;
for(i = 1 ; i <= n ; ++i){
for(j = 1 ; j <= n ; ++j){
if(map[i][j] == temp)
map[i][j] = map[j][i];
}
}
????int ans = dijkstra(1,5); ?
????printf("%d",ans); ?
????return 0; ?
}
/* 邊的數(shù)據(jù)
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 6 2
5 6 9
4 5 6
3 4 11
*/
