圖示：

模版：

1 /* 2 Dijkstra計算單源最短路徑，并記錄路徑 3 4 m個點，n條邊，每條邊上的權值非負，求起點st到終點et的最短路徑 5 6 input: 7 n m st et 8 6 10 1 6 9 1 2 6 10 1 3 2 11 1 4 1 12 2 3 6 13 2 5 3 14 3 4 2 15 3 5 2 16 3 6 4 17 4 6 5 18 5 6 3 19 20 output: 21 6 22 1-->4-->6 23 */ 24 25 26 27 #include<iostream> 28 #include<stdio.h> 29 #include<cstring> 30 using namespace std; 31 32 #define INF 0xfffffff 33 #define MAXN 1010 34 35 int n,m; /*n:點數,m:邊數*/ 36 int st,et; /*st:起點,et:終點*/ 37 int weight[MAXN][MAXN]; /*保存的是邊權值*/ 38 int dis[MAXN]; /*保存源點到任意點之間的最短路*/ 39 int father[MAXN]; /*保存i點的父親節點*/ 40 int vis[MAXN]; /*記錄哪些頂點已經求過最短路*/ 41 42 43 void input() 44 { 45 scanf("%d%d%d%d",&n,&m,&st,&et); 46 int i,j; 47 for(i=1;i<=n;i++) 48 { 49 for(j=1;j<=n;j++) 50 weight[i][j]=INF; 51 weight[i][i]=0; 52 } 53 int start,end,value; 54 for(i=0;i<m;i++) 55 { 56 scanf("%d%d%d",&start,&end,&value); 57 if(weight[start][end]>value) //去重 58 weight[start][end]=weight[end][start]=value; //無向圖 59 } 60 } 61 62 void dijkstra() 63 { 64 int i,j; 65 memset(vis,0,sizeof(vis)); 66 memset(father,0,sizeof(father)); 67 68 //初始化dis數組 69 for(i=1;i<=n;i++) 70 dis[i]=INF; 71 dis[st]=0; 72 73 //枚舉n個點 74 for(i=1;i<=n;i++) 75 { 76 int pos=-1; 77 78 //找到未加入集合的最短路的點 79 for(j=1;j<=n;j++) 80 if(!vis[j]&&(pos==-1||dis[j]<dis[pos])) 81 pos=j; 82 83 //標記這個點已經走過 84 vis[pos]=1; 85 86 //更新dis 87 for(j=1;j<=n;j++) 88 if(!vis[j]&&(dis[j]>dis[pos]+weight[pos][j])) 89 { 90 dis[j]=dis[pos]+weight[pos][j]; 91 father[j]=pos; 92 } 93 } 94 } 95 96 void output() 97 { 98 printf("%d\n",dis[et]); 99 int que[MAXN]; 100 int cnt=0; 101 int tmp=et; 102 while(father[tmp]!=0) 103 { 104 que[cnt++]=tmp; 105 tmp=father[tmp]; 106 } 107 int i; 108 printf("%d",st); 109 for(i=cnt-1;i>=0;i--) 110 printf("-->%d",que[i]); 111 printf("\n"); 112 } 113 114 115 int main() 116 { 117 input(); 118 dijkstra(); 119 output(); 120 return 0; 121 }

?

?

---

?

變形1：PAT 1030:http://www.patest.cn/contests/pat-a-practise/1030

題意：在原有計算weight的基礎之上，再添加一個cost，最短路不唯一時，cost取最小。

分析：

?

1 #include<stack> 2 #include<stdio.h> 3 using namespace std; 4 5 #define MAXN 502 6 #define INF 0xfffffff 7 8 int n,m,s,d; 9 int weight[MAXN][MAXN]; 10 int cost[MAXN][MAXN]; 11 int dis[MAXN]; 12 int cos[MAXN]; 13 int pre[MAXN]; 14 int vis[MAXN]; 15 16 void init() 17 { 18 int i,j; 19 for(i=0;i<n;i++) 20 { 21 for(j=0;j<n;j++) 22 { 23 weight[i][j]=INF; 24 cost[i][j]=INF; 25 } 26 } 27 } 28 29 void input() 30 { 31 int i,j; 32 33 scanf("%d%d%d%d",&n,&m,&s,&d); 34 35 init(); 36 37 for(i=0;i<m;i++) 38 { 39 int st,et,di,co; 40 scanf("%d%d%d%d",&st,&et,&di,&co); 41 if(di<weight[st][et]) 42 { 43 weight[st][et]=weight[et][st]=di; 44 cost[st][et]=cost[et][st]=co; 45 } 46 else if(di==weight[st][et]&&co<cost[st][et]) 47 { 48 cost[st][et]=cost[et][st]=co; 49 } 50 } 51 } 52 53 void dijkstra() 54 { 55 int i,j; 56 57 for(i=0;i<n;i++) 58 { 59 vis[i]=0; 60 pre[i]=-1; 61 dis[i]=weight[s][i]; 62 cos[i]=cost[s][i]; 63 } 64 65 vis[s]=1; 66 67 int mindist,pos; 68 69 for(i=0;i<n;i++) 70 { 71 mindist=INF; 72 for(j=0;j<n;j++) 73 { 74 if(!vis[j]&&mindist>dis[j]) 75 { 76 mindist=dis[j]; 77 pos=j; 78 } 79 } 80 81 vis[pos]=1; 82 83 if(pos==d) 84 { 85 return ; 86 } 87 88 for(j=0;j<n;j++)89 {90 if(!vis[j]&&weight[pos][j]<INF)91 {92 if(dis[j]>dis[pos]+weight[pos][j])93 {94 dis[j]=dis[pos]+weight[pos][j];95 cos[j]=cos[pos]+cost[pos][j];96 pre[j]=pos;97 }98 else if(dis[j]==dis[pos]+weight[pos][j]) 99 { 100 if(cos[j]>cos[pos]+cost[pos][j]) 101 { 102 cos[j]=cos[pos]+cost[pos][j]; 103 pre[j]=pos; 104 } 105 } 106 } 107 } 108 } 109 } 110 111 void output() 112 { 113 stack<int>sta; 114 int p=d; 115 while(p!=-1) 116 { 117 sta.push(p); 118 p=pre[p]; 119 } 120 121 printf("%d",s); 122 while(!sta.empty()) 123 { 124 printf(" %d",sta.top()); 125 sta.pop(); 126 } 127 128 printf(" %d %d\n",dis[d],cos[d]); 129 } 130 131 int main() 132 { 133 input(); 134 if(s==d) 135 { 136 printf("%d %d 0 0\n",s,d); 137 return 0; 138 } 139 dijkstra(); 140 output(); 141 return 0; 142 }

?

?

?

---

?

變形2：PAT 1018：http://pat.zju.edu.cn/contests/pat-a-practise/1018

轉載于:https://www.cnblogs.com/XBWer/p/4088368.html

總結

以上是生活随笔為你收集整理的【图算法】Dijkstra算法及变形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。