Dijkstra演算法2-有解無憂

  1 // 再來一手精髓的Dijkstra
  2 // 復雜度O( E*log(V) )
  3 
  4 #include <cstdio>
  5 #include <iostream>
  6 #include <vector>
  7 #include <queue>
  8 
  9 using namespace std;
 10 
 11 const int max_N = 1000+2;
 12 const int max_E = 10000+2;
 13 const int INF = 1e9;
 14 
 15 int N,E;
 16 int d[max_N];
 17 
 18 // 來自何方，已經不重要了，
 19 // 實際上是在鄰接表實作的程序中，行號即為來自的頂點
 20 struct edge
 21 {
 22     int to,cost;
 23 };
 24 // P.first代表距離，P.second代表頂點編號
 25 typedef pair<int,int> P;
 26 
 27 vector<edge> G[max_N];
 28 
 29 // 這一個演算法下來，我們在陣列d中得到了從s點到其余所有頂點的最短路程
 30 void dijkstra(int s)
 31 {
 32     // 建立最堆，來維護最小距離，可以降低一層復雜度
 33     priority_queue< P,vector<P>,greater<P> > que;
 34 
 35     fill(d,d+N,INF);
 36     d[s]=0;
 37     que.push(P(0,s));
 38 
 39     while(!que.empty())
 40     {
 41         // 取出一個頂點，看是否是Dijstra演算法中，已經確定的最小頂點
 42         P p=que.top();
 43         que.pop();
 44 
 45         int v=p.second;
 46         // 讓我們來看看這一步
 47         // 首先，每次取出堆中的最小元素
 48         // 然后去檢索這個堆頂元素的標號所對應的距離
 49         // 咦，你會發現堆頂這個距離，竟然比取出的最小元素還要小
 50         // 驚訝？難道出錯了？沒有，考慮Dijkstra演算法的流程，這個頂點肯定是之前已經確定過的最小頂點了，不需要考慮
 51         // 之前的實作是多加了一個flag陣列來標記，這里可以省去這部分記憶體，直接用這個條件來判斷
 52         if(d[v]<p.first)
 53         {
 54             continue;
 55         }
 56 
 57         for(int i=0;i<G[v].size();++i)
 58         {
 59             edge e=G[v][i];
 60             if(d[e.to] > d[v] + e.cost)
 61             {
 62                 d[e.to]=d[v]+e.cost;
 63                 // 陣列中維護此次被更新的節點即可，其余節點不需要維護
 64                 que.push(P(d[e.to],e.to));
 65             }
 66         }
 67     }
 68 
 69 }
 70 
 71 int main()
 72 {
 73     int a,b,c;
 74     scanf("%d %d",&N,&E);
 75     for(int i=0;i<E;++i)
 76     {
 77         scanf("%d %d %d",&a,&b,&c);
 78         edge e;
 79         e.to=b;
 80         e.cost=c;
 81         G[a].push_back(e);
 82         // 無向圖
 83         e.to=a;
 84         e.cost=c;
 85         G[b].push_back(e);
 86     }
 87 
 88     dijkstra(0);
 89 
 90     for(int i=0;i<N;++i)
 91     {
 92         printf("%d ",d[i]);
 93     }
 94 
 95     return 0;
 96 }
 97 
 98 /*
 99 7 10
100 0 1 2
101 0 2 5
102 1 2 4
103 1 3 6
104 1 4 10
105 2 3 2
106 3 5 1
107 4 5 3
108 4 6 5
109 5 6 9
110 
111 
112 */
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/61728.html
標籤：C++
上一篇：anniversary party_hdu1520
下一篇：#《Essential C++》讀書筆記# 第七章例外處理