首页 > > 程序设计 > C/C++ >

Dijkstra算法2

2020-02-16 16:00:45来源：博客园阅读 ()

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 */