最短路问题汇总
注意，这里为了方便描述算法，所以都用了最易理解的邻接矩阵来写，比赛中为了追求效率，一般将邻接矩阵改为链式前向星或者邻接表。
迪杰斯特拉算法 O(V^2)
1const int MAXN = 100;
2const int INF = 0x3f3f3f3f;
3// 有向无环图 DAG
4int V, E; // 顶点数和边数
5int graph[MAXN][MAXN]; // DAG邻接矩阵，初始值为INF，不可达为INF，否则为cost值
6int d[MAXN]; // 从某点s出发到其它任意结点的最短路径长度，初始值为INF
7int visited[MAXN]; // 某点是否访问过，访问过则为1否则为0
8
9// 初始化图
10void init() {
11 memset(graph, 0x3f, sizeof(graph));
12 cin >> V >> E;
13 int from, to, cost;
14 for (int i = 0 ; i < E; i++) {
15 cin >> from >> to >> cost;
16 graph[from][to] = cost;
17 }
18}
19// 迪杰斯特拉算法求解最短路，针对点展开
20void Dijkstra(int s) {
21 memset(d, 0x3f, sizeof(d));
22 memset(visited, 0, sizeof(visited));
23 visited[s] = 1;
24 for(int i = 0; i < V; i++) d[i] = graph[s][i];
25 d[s] = 0;
26 int k, min_cost;
27 // 无负边时最多更新n-1(其他结点数)次
28 for(int i = 0; i < V - 1; i++){
29 min_cost = INF;
30 // 寻找最未被访问的且权值最小的路径，需要优化的地方
31 for(int j = 0; j < V; j++){
32 if(!visited[j] && d[j] < min_cost){
33 k = j;
34 min_cost = d[j];
35 }
36 }
37 visited[k] = 1;
38 // 利用找到的结点更新最短路径
39 for(int j = 0; j < V; j++){
40 if(!visited[j] && min_cost + graph[k][j] < d[j]){
41 d[j] = min_cost + graph[k][j];
42 }
43 }
44 }
45}
迪杰斯特拉算法的堆优化 O(ElogV) 不含负权就用它 ~
1const int MAXN = 100;
2const int INF = 0x3f3f3f3f;
3// 有向无环图 DAG
4int V, E; // 顶点数和边数
5int graph[MAXN][MAXN]; // DAG邻接矩阵，初始值为INF，不可达为INF，否则为cost值
6int d[MAXN]; // 从某点s出发到其它任意结点的最短路径长度，初始值为INF
7int visited[MAXN]; // 某点是否访问过，访问过则为1否则为0
8
9typedef pair<int, int> P; // first: 最短距离 second：通往的顶点编号
10priority_queue<P, vector<P>, greater<P> > que; // greater<T> 从小到大取出
11
12// 初始化图
13void init() {
14 memset(graph, 0x3f, sizeof(graph));
15 cin >> V >> E;
16 int from, to, cost;
17 for (int i = 0 ; i < E; i++) {
18 cin >> from >> to >> cost;
19 graph[from][to] = cost;
20 }
21}
22// 迪杰斯特拉算法堆优化求解最短路，针对点展开
23void Dijkstra_optimise(int s) {
24 memset(d, 0x3f, sizeof(d));
25 memset(visited, 0, sizeof(visited));
26 // for(int i = 0; i < V; i++) d[i] = graph[s][i];
27 // 开始min_cost为0，若加上这一步，0 + graph[k][i] == d[i] == graph[k][i]，导致无法更新队列
28 d[s] = 0;
29 int k, min_cost;
30 que.push(P(0, s));
31 while (!que.empty()) {
32 P p = que.top(); que.pop();
33 // 通过堆优化直接获得了目标
34 min_cost = p.first;
35 k = p.second;
36 // 若已经有更短的路径则不更新
37 if (min_cost > d[k]) continue;
38 visited[k] = 1;
39 for (int i = 0; i < V; i++) {
40 if (!visited[i] && min_cost + graph[k][i] < d[i]) {
41 d[i] = graph[k][i] + min_cost;
42 que.push(P(d[i], i));
43 }
44 }
45 }
46}
贝尔曼福德算法 O(VE)
1using namespace std;
2const int MAXN = 100;
3const int MAXE = 100;
4const int INF = 0x3f3f3f3f;
5// 有向无环图 DAG
6struct Edge {
7 int from, to, cost;
8};
9int V, E; // 顶点数和边数
10int d[MAXN]; // 从某点s出发到其它任意结点的最短路径长度，初始值为INF
11Edge edge[MAXE]; // 边集
12
13// 初始化图
14void init() {
15 cin >> V >> E;
16 int from, to, cost;
17 for (int i = 0 ; i < E; i++)
18 cin >> edge[i].from >> edge[i].to >> edge[i].cost;
19}
20// 贝尔曼福德算法求解最短路，针对边展开
21void Bellman_Ford(int s)
22{
23 memset(d, 0x3f, sizeof(d));
24 d[s] = 0;
25 while (1) {
26 int flag = 0;
27 // DAG下最少更新E次
28 for (int i = 0; i < E; i++) {
29 Edge e = edge[i];
30 if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
31 d[e.to] = d[e.from] + e.cost;
32 flag = 1;
33 }
34 }
35 // 如果没出现更新则退出
36 if (!flag) break;
37 }
38}
贝尔曼福德算法优化（SPFA + 优先队列）含负边就用它~
虽然大家都说SPFA已死，但其实是说笑罢了，含负权边或者负环的题还真离不开这东西~
1const int MAXN = 100;
2const int INF = 0x3f3f3f3f;
3// 有向无环图 DAG
4int V, E; // 顶点数和边数
5int graph[MAXN][MAXN]; // DAG邻接矩阵，初始值为INF，不可达为INF，否则为cost值
6int d[MAXN]; // 从某点s出发到其它任意结点的最短路径长度，初始值为INF
7int vis[MAXN]; // 结点是否已入队
8int push_count[MAXN]; // 结点入队次数，若大于等于V，则证明存在负环
9priority_queue<int, vector<int>, greater<int> > que; // greater<T> 从小到大取出
10
11// 初始化图
12void init() {
13 memset(graph, 0x3f, sizeof(graph));
14 cin >> V >> E;
15 int from, to, cost;
16 for (int i = 0 ; i < E; i++) {
17 cin >> from >> to >> cost;
18 graph[from][to] = cost;
19 }
20}
21// SPFA算法求解最短路
22void SPFA(int s) {
23 memset(d, 0x3f, sizeof(d));
24 memset(vis, 0, sizeof(vis));
25 memset(push_count, 0, sizeof(push_count));
26 d[s] = 0;
27 que.push(s);
28 vis[s] = 1;
29 push_count[s]++;
30 while (!que.empty()) {
31 int flag = 0; // 负环判断
32 int v = que.top(); que.pop(); vis[v] = 0;
33 for (int i = 0; i < V; i++) {
34 if (d[v] + graph[v][i] < d[i]) {
35 d[i] = d[v] + graph[v][i];
36 if (!vis[i]) {
37 que.push(i);
38 vis[i] = 1;
39 push_count[i]++;
40 if (push_count[i] >= V) {
41 flag = 1;
42 break;
43 }
44 }
45 }
46 }
47 if (flag) {
48 cout << "有负环" << endl;
49 break;
50 }
51 }
52}
弗洛伊德算法 O(V^3) 多源问题可以考虑用它~
1const int MAXN = 100;
2const int INF = 0x3f3f3f3f;
3// 有向无环图 DAG
4int V, E; // 顶点数和边数
5int graph[MAXN][MAXN]; // DAG邻接矩阵，初始值为INF，不可达为INF，否则为cost值
6int d[MAXN][MAXN]; // 从任意结点出发到其它任意结点的最短路径长度，初始值为INF
7
8// 初始化图
9void init() {
10 memset(graph, 0x3f, sizeof(graph));
11 cin >> V >> E;
12 int from, to, cost;
13 for (int i = 0 ; i < E; i++) {
14 cin >> from >> to >> cost;
15 graph[from][to] = cost;
16 }
17}
18// 弗洛伊德算法求解最短路
19void Floyd()
20{
21 // 初始化矩阵d
22 memset(d, 0x3f, sizeof(d));
23 for(int i = 0; i < V; i++)
24 for(int j = 0; j < V; j++)
25 d[i][j] = graph[i][j];
26 for(int k = 0; k < V; k++){//以顶点k为中转
27 for(int i = 0; i < V; i++){//从顶点i到顶点j
28 for(int j = 0; j < V; j++){
29 if (d[i][j] > d[i][k] + d[k][j])
30 d[i][j] = d[i][k] + d[k][j];
31 }
32 }
33 }
34}
附：
链式前向星
1const int MAXN = 100;
2struct Edge {
3 int to; // 边的终点
4 int next; // 与该边同起点的下一条边的编号
5 int w; // 边的权值
6};
7Edge edge[MAXN]; // 所有边的集合
8int head[MAXN]; // 所有起点的第一条边的编号，初始化为-1
9int V, E;
10// 建立图
11void build() {
12 int from, to, w, cnt = 0;
13 for (int i = 0; i < E; i++) {
14 cin >> from >> to >> w;
15 edge[cnt].to = to;
16 edge[cnt].w = w;
17 edge[cnt].next = head[from];
18 // 因此可将head初始化为-1，当next为-1时代表以该点为起点的边访问结束
19 head[from] = cnt++;
20 }
21}
22// 遍历整个图
23void traverse() {
24 for (int i = 0; i < V; i++) {
25 for (int j = head[i]; j != -1; j = edge[j].next) {
26 cout << " from " << i << " to " << edge[j].to << " weight: " << edge[j].w << endl;
27 }
28 }
29}
30// 遍历某个结点的邻接点
31void traverse_v(int v) {
32 for (int i = head[v]; i != -1; i = edge[i].next) {
33 cout << " from " << v << " to " << edge[i].to << " weight: " << edge[i].w << endl;
34 }
35}