迪杰斯特拉算法（Dijkstra）

佚名 5年前 (2019-05-29) 算法 1620人围观抢沙发百度已收录

模板一：

时间复杂度O（n²）

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 1 int dijkstra(int s,int m)  //s为起点,m为终点
 2 {
 3     memset(dist,0,sizeof(dist));   //初始化，dist数组用来储存s到各个点的距离
 4     memset(v,0,sizeof(v));         //初始化v数组，是否已标记
 5     for(int i=1;i<=n;++i)          //++i返回的是引用，稍微快一点
 6     {
 7         dist[i]=e[s][i];           //初始化，e[s][i]数组表示是点s到点i的权值，数组e用来存有向图或无向图的权值，用INF初始化
 8     }
 9     for(int i=1;i<=n;++i)
10     {
11         k=INF,u=0;
12         for(int j=1;j<=n;++j)      //找出当前dist最小的点
13         {
14             if(!v[j]&&dist[j]<k)
15             {
16                 k=dist[j];
17                 u=j;
18             }
19         }
20         v[u]=1;                    //标记
21         for(int j=1;j<=n;++j)      //更新与点u相连的点的权值和
22         {
23             if(!v[j]&&e[u][j]<INF&&dist[u]+e[u][j]<dist[j])    //比较从点s到点u载到点j的权值和点s直接到点j的权值
24             {
25                 dist[j]=dist[u]+e[u][j];
26             }
27         }
28     }
29     return dist[m];  
30 }

模板二：

时间复杂度 O（mlogn）m为边数，n为顶点数。

对于稀疏图的效果显著，对稠密图慎用。

 1 const int INF = 0x3f3f3f3f;
 2 const int maxn = 150;
 3 struct Edge
 4 {
 5     int from, to, dist;
 6     Edge(int u, int v, int d) :from(u), to(v), dist(d) {}
 7 };
 8 struct HeapNode
 9 {
10     int d, u;
11     HeapNode(int D,int U):d(D),u(U){}
12     bool operator < (const HeapNode& rhs) const {
13         return d > rhs.d;
14     }
15 };
16 struct Dijkstra
17 {
18     int n, m;
19     vector<Edge> edges;
20     vector<int> G[maxn];    //maxn要大于顶点数
21     bool done[maxn];
22     int d[maxn];
23     int p[maxn];
24 
25     void init(int n)
26     {
27         this->n = n;
28         for (int i = 0; i < n; ++i)
29             G[i].clear();
30         edges.clear();
31     }
32 
33     void addEdge(int from, int to, int dist)
34     {
35         edges.push_back(Edge(from, to, dist));
36         m = edges.size();
37         G[from].push_back(m - 1);
38     }
39 
40     void dijkstra(int s, int kk)          //s为起点 kk为终点
41     {
42         priority_queue<HeapNode> Q;
43         for (int i = 0; i < n; ++i)
44             d[i] = INF;
45         d[s] = 0;
46         memset(done, 0, sizeof(done));
47         Q.push(HeapNode( 0, s ));
48         while (!Q.empty())
49         {
50             HeapNode x = Q.top();
51             Q.pop();
52             int u = x.u;
53             if (u == kk)                  //到终点就退出
54             {
55                 printf("%d\n", x.d);
56                 break;
57             }
58             if (done[u])
59             {
60                 continue;
61             }
62             done[u] = true;
63             for (int i = 0; i < G[u].size(); ++i)
64             {
65                 Edge& e = edges[G[u][i]];
66                 if (d[u] + e.dist < d[e.to])
67                 {
68                     d[e.to] = d[u] + e.dist;
69                     p[e.to] = G[u][i];
70                     Q.push(HeapNode(d[e.to], e.to ));
71                 }
72             }
73         }
74     }
75 
76 };

放一道模板题

http://acm.hdu.edu.cn/showproblem.php?pid=2544

AC代码

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 using namespace std;
  8 const int INF = 0x3f3f3f3f;
  9 const int maxn = 150;
 10 struct Edge
 11 {
 12     int from, to, dist;
 13     Edge(int u, int v, int d) :from(u), to(v), dist(d) {}
 14 };
 15 struct HeapNode
 16 {
 17     int d, u;
 18     HeapNode(int D,int U):d(D),u(U){}
 19     bool operator < (const HeapNode& rhs) const {
 20         return d > rhs.d;
 21     }
 22 };
 23 struct Dijkstra
 24 {
 25     int n, m;
 26     vector<Edge> edges;
 27     vector<int> G[maxn];    //maxn要大于顶点数
 28     bool done[maxn];
 29     int d[maxn];
 30     int p[maxn];
 31 
 32     void init(int n)
 33     {
 34         this->n = n;
 35         for (int i = 0; i < n; ++i)
 36             G[i].clear();
 37         edges.clear();
 38     }
 39 
 40     void addEdge(int from, int to, int dist)
 41     {
 42         edges.push_back(Edge(from, to, dist));
 43         m = edges.size();
 44         G[from].push_back(m - 1);
 45     }
 46 
 47     void dijkstra(int s, int kk)          //s为起点 kk为终点
 48     {
 49         priority_queue<HeapNode> Q;
 50         for (int i = 0; i < n; ++i)
 51             d[i] = INF;
 52         d[s] = 0;
 53         memset(done, 0, sizeof(done));
 54         Q.push(HeapNode( 0, s ));
 55         while (!Q.empty())
 56         {
 57             HeapNode x = Q.top();
 58             Q.pop();
 59             int u = x.u;
 60             if (u == kk)
 61             {
 62                 printf("%d\n", x.d);
 63                 break;
 64             }
 65             if (done[u])
 66             {
 67                 continue;
 68             }
 69             done[u] = true;
 70             for (int i = 0; i < G[u].size(); ++i)
 71             {
 72                 Edge& e = edges[G[u][i]];
 73                 if (d[u] + e.dist < d[e.to])
 74                 {
 75                     d[e.to] = d[u] + e.dist;
 76                     p[e.to] = G[u][i];
 77                     Q.push(HeapNode(d[e.to], e.to ));
 78                 }
 79             }
 80         }
 81     }
 82 
 83 };
 84 int n, m, x, y, k;
 85 Dijkstra d;
 86 int main()
 87 {
 88     while (cin>>n>>m)
 89     {
 90         d.init(n);
 91         if (n == 0 && m == 0)
 92             break;
 93         while (m--)
 94         {
 95             cin >> x >> y >> k;
 96             d.addEdge(x - 1, y - 1, k);
 97             d.addEdge(y - 1, x - 1, k);
 98         }
 99         d.dijkstra(0, n - 1);
100     }
101     return 0;
102 }