Dijkstra算法优先队列实现与Bellman_Ford队列实现的理解
生活随笔
收集整理的這篇文章主要介紹了
Dijkstra算法优先队列实现与Bellman_Ford队列实现的理解
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
1 /*
2 Dijkstra算法用優(yōu)先隊(duì)列來實(shí)現(xiàn)，實(shí)現(xiàn)了每一條邊最多遍歷一次。 要知道，我們從隊(duì)列頭部找到的都是到
3 已經(jīng)"建好樹"的最短距離以及該節(jié)點(diǎn)編號, 并由該節(jié)點(diǎn)去更新 樹根 到其他點(diǎn)（被更新的節(jié)點(diǎn)可以在隊(duì)列中
4 ，也可以是非隊(duì)列中的節(jié)點(diǎn)）的距離 。
5
6 如果v節(jié)點(diǎn)的到更新，則直接放入隊(duì)列中（pair<d[v], v>）不會重復(fù)放入到隊(duì)列中
7
8 如果某個節(jié)點(diǎn)從隊(duì)列中出來的時候，如果cur.first != dist[cur.second] 就是 cur.second這個節(jié)點(diǎn)一開始
9 被更新的最短距離值 和 現(xiàn)在得到的最短距離的值dist[cur.second] 不想等，說明該節(jié)點(diǎn)已經(jīng)被之前隊(duì)列中
10 具有更短距離的節(jié)點(diǎn)更新過了， 那么新的節(jié)點(diǎn)pair(dist[cur.second], cur.second)再次放入優(yōu)先隊(duì)列中，用來跟新其他節(jié)點(diǎn)的最短距離。 如果想等，則dist[cur.second]就是cur.second最終的最短距離！
11 */
12 #include<iostream>
13 #include<queue>
14 #include<cstring>
15 #define N 1000
16 using namespace std;
17
18 class EDGE
19 {
20 public:
21 int u, v, w;
22 int next;//和節(jié)點(diǎn) u 相連的下一條邊的編號
23 };
24
25 EDGE edge[2*N];
26
27 typedef pair<int, int>pii;//pair<距離，節(jié)點(diǎn)號>
28
29 int first[N];//最多有N個節(jié)點(diǎn) ,建立每個節(jié)點(diǎn)和其相連的邊的關(guān)系
30 int dist[N];//源點(diǎn)到各個點(diǎn)的最短距離
31
32 int n, m;//節(jié)點(diǎn)數(shù)，邊數(shù)
33
34 bool operator >(pii a, pii b)
35 {
36 if(a.first==b.first)
37 return a.second > b.second;
38 return a.first > b.first;//按照最短的距離值在隊(duì)列的前段
39 }
40
41 priority_queue<pii, vector<pii>, greater<pii> >q;
42
43 void Dijkstra()
44 {
45 pii cur;
46 memset(dist, 0x3f, sizeof(dist));
47 dist[1]=0;//另節(jié)點(diǎn) 1 為源點(diǎn)
48 q.push(make_pair(0, 1));
49 while(!q.empty())
50 {
51 cur=q.top();
52 q.pop();
53 if(cur.first != dist[cur.second]) continue;// 不等于的話說明該節(jié)點(diǎn)的值已經(jīng)經(jīng)過其他節(jié)點(diǎn)松弛為更短的距離值了
54 for(int e=first[cur.second]; e!=-1; e=edge[e].next)
55 if(dist[edge[e].v]>dist[edge[e].u]+edge[e].w)
56 {
57 dist[edge[e].v]=dist[edge[e].u]+edge[e].w;
58 q.push(make_pair(dist[edge[e].v], edge[e].v));//將更新之后的節(jié)點(diǎn)的放入隊(duì)列之中
59 }
60 }
61 }
62
63 int main()
64 {
65 int i;
66 cin>>n>>m;
67 for(i=1; i<=n; ++i)
68 first[i]=-1;
69 for(i=0; i<m; ++i)
70 {
71 cin>>edge[i].u>>edge[i].v>>edge[i].w;
72 edge[edge[i].u].next=first[edge[i].u];
73 first[edge[i].u]=i;
74 }
75 Dijkstra();
76 for(i=2; i<=n; ++i)
77 cout<<"1->"<<i<<":"<<dist[i]<<endl;
78 return 0;
79 } 1 /*
2 Bellman_Ford算法用隊(duì)列實(shí)現(xiàn)和 Dijkstra算法用優(yōu)先隊(duì)列來實(shí)現(xiàn)相同的地方是，都是 層次 更新到節(jié)點(diǎn)的最短距離，
3 都是將具有最短距離的節(jié)點(diǎn)（如果不在隊(duì)列中）放入隊(duì)列中 4 Bellman_Ford算法中實(shí)現(xiàn)的是帶有負(fù)權(quán)圖的最短距離，因?yàn)樨?fù)權(quán)的關(guān)系，這樣可能使得某個 5 節(jié)點(diǎn)的最短路徑的值一直被更新（比如存在負(fù)權(quán)回路的時候），所以被更新的節(jié)點(diǎn)（如果不在隊(duì)列中）一直會進(jìn)入隊(duì)列中 6 */ 7 #include<iostream> 8 #include<queue> 9 #include<cstring> 10 #define N 1000 11 using namespace std; 12 13 class EDGE 14 { 15 public: 16 int u, v, w; 17 int next;//和節(jié)點(diǎn) u 相連的下一條邊的編號 18 }; 19 20 EDGE edge[2*N]; 21 22 int first[N];//最多有N個節(jié)點(diǎn) ,建立每個節(jié)點(diǎn)和其相連的邊的關(guān)系 23 int dist[N];//源點(diǎn)到各個點(diǎn)的最短距離 24 int cnt[N];//記錄每個節(jié)點(diǎn)在隊(duì)列中出現(xiàn)的次數(shù) 25 int vis[N];//記錄當(dāng)前的節(jié)點(diǎn)是否已經(jīng)在隊(duì)列中 26 27 int n, m;//節(jié)點(diǎn)數(shù)，邊數(shù) 28 29 30 queue<int>q; 31 32 int Bellman_Ford() 33 { 34 int cur; 35 memset(dist, 0x3f, sizeof(dist)); 36 dist[1]=0;//另節(jié)點(diǎn) 1 為源點(diǎn) 37 q.push(1); 38 while(!q.empty()) 39 { 40 cur=q.front(); 41 q.pop(); 42 vis[cur]=0;//出隊(duì)列 43 ++cnt[cur]; 44 if(cnt[cur]>n-1)//如果不存在負(fù)權(quán)回路，那么某個節(jié)點(diǎn)的最多被更新的次數(shù)為 n-1 次 45 return 0; 46 for(int e=first[cur]; e!=-1; e=edge[e].next) 47 if(dist[edge[e].v]>dist[edge[e].u]+edge[e].w) 48 { 49 dist[edge[e].v]=dist[edge[e].u]+edge[e].w; 50 if(!vis[edge[e].v])//本跟新的節(jié)點(diǎn)沒有在隊(duì)列中 51 { 52 q.push(edge[e].v);//將更新之后的節(jié)點(diǎn)的放入隊(duì)列之中 53 vis[edge[e].v]=1;//放入隊(duì)列 54 } 55 } 56 } 57 return 1; 58 } 59 60 int main() 61 { 62 int i; 63 cin>>n>>m; 64 for(i=1; i<=n; ++i) 65 first[i]=-1; 66 for(i=0; i<m; ++i) 67 { 68 cin>>edge[i].u>>edge[i].v>>edge[i].w; 69 edge[edge[i].u].next=first[edge[i].u]; 70 first[edge[i].u]=i; 71 } 72 if(!Bellman_Ford())//表示存在負(fù)權(quán)回路 73 cout<<"不存在最短路徑"<<endl; 74 else 75 { 76 for(i=2; i<=n; ++i) 77 cout<<"1->"<<i<<":"<<dist[i]<<endl; 78 } 79 return 0; 80 }
3 都是將具有最短距離的節(jié)點(diǎn)（如果不在隊(duì)列中）放入隊(duì)列中 4 Bellman_Ford算法中實(shí)現(xiàn)的是帶有負(fù)權(quán)圖的最短距離，因?yàn)樨?fù)權(quán)的關(guān)系，這樣可能使得某個 5 節(jié)點(diǎn)的最短路徑的值一直被更新（比如存在負(fù)權(quán)回路的時候），所以被更新的節(jié)點(diǎn)（如果不在隊(duì)列中）一直會進(jìn)入隊(duì)列中 6 */ 7 #include<iostream> 8 #include<queue> 9 #include<cstring> 10 #define N 1000 11 using namespace std; 12 13 class EDGE 14 { 15 public: 16 int u, v, w; 17 int next;//和節(jié)點(diǎn) u 相連的下一條邊的編號 18 }; 19 20 EDGE edge[2*N]; 21 22 int first[N];//最多有N個節(jié)點(diǎn) ,建立每個節(jié)點(diǎn)和其相連的邊的關(guān)系 23 int dist[N];//源點(diǎn)到各個點(diǎn)的最短距離 24 int cnt[N];//記錄每個節(jié)點(diǎn)在隊(duì)列中出現(xiàn)的次數(shù) 25 int vis[N];//記錄當(dāng)前的節(jié)點(diǎn)是否已經(jīng)在隊(duì)列中 26 27 int n, m;//節(jié)點(diǎn)數(shù)，邊數(shù) 28 29 30 queue<int>q; 31 32 int Bellman_Ford() 33 { 34 int cur; 35 memset(dist, 0x3f, sizeof(dist)); 36 dist[1]=0;//另節(jié)點(diǎn) 1 為源點(diǎn) 37 q.push(1); 38 while(!q.empty()) 39 { 40 cur=q.front(); 41 q.pop(); 42 vis[cur]=0;//出隊(duì)列 43 ++cnt[cur]; 44 if(cnt[cur]>n-1)//如果不存在負(fù)權(quán)回路，那么某個節(jié)點(diǎn)的最多被更新的次數(shù)為 n-1 次 45 return 0; 46 for(int e=first[cur]; e!=-1; e=edge[e].next) 47 if(dist[edge[e].v]>dist[edge[e].u]+edge[e].w) 48 { 49 dist[edge[e].v]=dist[edge[e].u]+edge[e].w; 50 if(!vis[edge[e].v])//本跟新的節(jié)點(diǎn)沒有在隊(duì)列中 51 { 52 q.push(edge[e].v);//將更新之后的節(jié)點(diǎn)的放入隊(duì)列之中 53 vis[edge[e].v]=1;//放入隊(duì)列 54 } 55 } 56 } 57 return 1; 58 } 59 60 int main() 61 { 62 int i; 63 cin>>n>>m; 64 for(i=1; i<=n; ++i) 65 first[i]=-1; 66 for(i=0; i<m; ++i) 67 { 68 cin>>edge[i].u>>edge[i].v>>edge[i].w; 69 edge[edge[i].u].next=first[edge[i].u]; 70 first[edge[i].u]=i; 71 } 72 if(!Bellman_Ford())//表示存在負(fù)權(quán)回路 73 cout<<"不存在最短路徑"<<endl; 74 else 75 { 76 for(i=2; i<=n; ++i) 77 cout<<"1->"<<i<<":"<<dist[i]<<endl; 78 } 79 return 0; 80 }
?
?
轉(zhuǎn)載于:https://www.cnblogs.com/hujunzheng/p/3781817.html
總結(jié)
以上是生活随笔為你收集整理的Dijkstra算法优先队列实现与Bellman_Ford队列实现的理解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 9.6米槽车车辆尺寸
- 下一篇： 华素三叶草有洗发水吗？？？