问题：
使用Dijkstra算法求由顶点a到顶点h的最短路径。
解析：
根据初始点，挨个的把离初始点最近的点一个一个找到并加入集合，集合中所有的点的dis[i]都是该点到初始点最短路径长度，由于后加入的点是根据集合S中的点为基础拓展的，所以也能找到最短路径。
设计（核心代码）：
1 void dijkstra(int s)
2 {
3 memset(dis, inf, sizeof dis);
4 memset(vis, 0, sizeof vis);
5 dis[s] = 0;
6 for (int i = 1; i <= n; ++i)
7 {
8 int min_p = -1, minn = inf;
9 for (int j = 1; j <= n; ++j)
10 {
11 if (!vis[j] && dis[j] < minn)
12 {
13 min_p = j;
14 minn = dis[j];
15 }
16 }
17 for (int j = 1; j <= n; ++j)
18 {
19 if (dis[j] > dis[min_p] + mp[min_p][j])
20 {
21 dis[j] = dis[min_p] + mp[min_p][j];
22 }
23 }
24 vis[min_p] = 1;
25 }
26 }
分析：
对于一个已知点a，n次更新。每次更新找到最短边，循环一次；用找到的最短边去更新，循环一次，但是这两次循环不是嵌套的关系，所以总的复杂度为O(n^2)。
源码：
https://github.com/Big-Kelly/Algorithm
1 #include<bits/stdc++.h>
2 #include <set>
3 #include <map>
4 #include <stack>
5 #include <cmath>
6 #include <queue>
7 #include <cstdio>
8 #include <string>
9 #include <vector>
10 #include <cstring>
11 #include <iostream>
12 #include <algorithm>
13
14 #define ll long long
15 #define pll pair<ll,ll>
16 #define pii pair<int,int>
17 #define bug printf("*********n")
18 #define FIN freopen("input.txt","r",stdin);
19 #define FON freopen("output.txt","w+",stdout);
20 #define IO ios::sync_with_stdio(false),cin.tie(0)
21 #define ls rt<<1
22 #define rs rt<<1|1
23 #define pb push_back
24 #define Q(a) cout<<a<<endl
25
26 using namespace std;
27 const int inf = 2e9 + 7;
28 const ll Inf = 1e18 + 7;
29 const int maxn = 1e3 + 5;
30 const int mod = 1e9 + 7;
31 const double eps = 1e-7;
32
33 int gcd(int a, int b)
34 {
35 return b ? gcd(b, a % b) : a;
36 }
37
38 ll lcm(ll a, ll b)
39 {
40 return a / gcd(a, b) * b;
41 }
42
43 ll read()
44 {
45 ll p = 0, sum = 0;
46 char ch;
47 ch = getchar();
48 while (1)
49 {
50 if (ch == '-' || (ch >= '0' && ch <= '9'))
51 break;
52 ch = getchar();
53 }
54
55 if (ch == '-')
56 {
57 p = 1;
58 ch = getchar();
59 }
60 while (ch >= '0' && ch <= '9')
61 {
62 sum = sum * 10 + ch - '0';
63 ch = getchar();
64 }
65 return p ? -sum : sum;
66 }
67
68 struct Dijkstra
69 {
70 int n;
71 int dis[maxn], vis[maxn];
72 int mp[maxn][maxn];
73
74 void dijkstra(int s)
75 {
76 memset(dis, inf, sizeof dis);
77 memset(vis, 0, sizeof vis);
78 dis[s] = 0;
79 for (int i = 1; i <= n; ++i)
80 {
81 int min_p = -1, minn = inf;
82 for (int j = 1; j <= n; ++j)
83 {
84 if (!vis[j] && dis[j] < minn)
85 {
86 min_p = j;
87 minn = dis[j];
88 }
89 }
90 for (int j = 1; j <= n; ++j)
91 {
92 if (dis[j] > dis[min_p] + mp[min_p][j])
93 {
94 dis[j] = dis[min_p] + mp[min_p][j];
95 }
96 }
97 vis[min_p] = 1;
98 }
99 }
100 };
101
102 int main()
103 {
104 int n, m;
105 scanf("%d %d", &n, &m);
106 Dijkstra d;
107 d.n = n;
108 memset(d.mp, inf, sizeof d.mp);
109 while (m--)
110 {
111 int u, v, w;
112 scanf("%d %d %d", &u, &v, &w);
113 d.mp[u][v] = d.mp[v][u] = w;
114 }
115 d.dijkstra(1);
116 int q;
117 scanf("%d", &q);
118 while (q--)
119 {
120 int ask;
121 scanf("%d", &ask);
122 printf("%dn", d.dis[ask]);
123 }
124 }
View Code
原文链接: https://www.cnblogs.com/zhang-Kelly/p/12450939.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/372151
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
