shortest-path-algorithm

shortest-path-algorithm

Charles Lv7
  2023-01-05 11:06:11 2023-01-05 11:06:11 Created   2023-07-30 10:53:16 2023-07-30 10:53:16 Updated      2.3k Words  11 Mins  

shortest-path-algorithm

最短路径算法

1.Floyd

算法思路

Floyd算法是一种非常简单的算法，采用了动态规划的思想。假设Ai和Aj两点间不包含其他顶点。加入顶点B能够使得Ai-B-Aj的距离小于Ai-Aj，则最短路径中应该包括B。顶点B是从1到N的。假设有最短路径A-1-N-B，先插入1时能够对A-B和A-N进行优化，再插入N时会先对1-B进行优化，从而对A-B的距离进行了优化。同理假设有最短路径A-N-1-B，先插入1对N-B的距离进行优化，再插入N对A-1和A-B（因为上一步对B-B进行了优化）进行了优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Floyd_Warshall(vector<int> g[], int n) {
    // initial
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                g[i][j] = 0;
            } else {
                g[i][j] = INF;
            }
        }
    }
    // Floyd_Warshall
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (g[i][j] > g[i][k] + g[k][j]) {
                    g[i][j] = g[i][k] + g[k][j];
                }
            }
        }
    }
}

2.Dijkstra

算法思路

Dijkstra算法与生成最小生成树的Prim算法很像。在Prim算法中，是每次都将距离当前最小生成树距离最近的顶点及其边加入到生成树T中。而在Dijkstra算法中，是每次将距离当前路径最近的顶点加入最短路径中。不同的是，在加入顶点的同时还需要遍历加入顶点的邻接顶点以更新其他顶点到当前最短路径的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int book[M];
void Dijkstra(vector<int> g[], int n, int origin, int dis[]) {
    // initial
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                g[i][j] = 0;
            } else {
                g[i][j] = INF;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        dis[i] = g[origin][i];
    }  // node origin->every nodes
    for (int i = 1; i <= n; i++)
        book[i] = 0;
    book[origin] = 1;
    // Dijkstra
    for (int i = 1; i <= n - 1; i++) {
        int min_dis = INF, u;
        for (int j = 1; j <= n; j++) {
            if (!book[j] && dis[j] < min_dis) {
                min_dis = dis[j];
                u = j;
            }
        }
        book[u] = 1;
        for (int j = 1; j <= n; j++) {
            if (g[u][j] < INF) {
                if (dis[j] > dis[u] + g[u][j]) {
                    dis[j] = dis[u] + g[u][j];
                }
            }
        }
    }
}

Dijkstra的堆优化(后续补充部分)

稀疏图，用邻接矩阵会内存超限，所以要使用邻接表，但是仅仅邻接表又会面临时间超限，所以还要在进行堆优化（即利用优先队列中的小根堆进行优化），堆优化后时间复杂度为O(mlog(n))。

用堆对dis数组进行维护,用O($log_2{n}$)的时间取出堆顶元素并删除,用O($log_2{n}$)遍历每条边,总复杂度$O((n+m)*(log_2{n}))$

注意优先队列选用小根堆(greater)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
const int N = 150005;
struct MyStruct{
	int y;
	int l;
};
int n, m;
typedef pair<int, int> P;
vector<MyStruct> r[N];
int dis[N];
priority_queue<P, vector<P>, greater<P> >que;
//小根堆，升序排序，对于pair类型，先比较第一个元素，第一个元素相同比较第二个元素。
void dijkstra(){
	while (!que.empty()){
		if (dis[que.top().second] < que.top().first){
            //当已知最短路小于此时队列中最短路时，跳过并将其出队。
			que.pop();
			continue;
		}				
		for (int i = 0; i<r[que.top().second].size(); i++){
			if (dis[r[que.top().second][i].y] > dis[que.top().second] + r[que.top().second][i].l){
				dis[r[que.top().second][i].y] = dis[que.top().second] + r[que.top().second][i].l;
				que.push({dis[r[que.top().second][i].y], r[que.top().second][i].y});
			}
		}
		que.pop();
	}
}
int main(){
	cin >> n >> m;
	memset(dis, 0x3f, sizeof(dis));
	for (int i = 1; i <= n; i++)
		r[i].clear();//清空vector数组
	for (int i = 0; i < m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		r[a].push_back({b,c});//有向图
		//无向图再加上r[b].push_back({a,c})即可
	}
	dis[1] = 0;
	que.push({0, 1});//0为dis[1]的值即此时最短路径，1为当前点。
	dijkstra();
	if(dis[n]<0x3f3f3f3f)
	cout << dis[n] << endl;
	else
	cout<<"-1"<<endl;
	return 0;
}

3.Bellman-Ford

算法思路

而Bellman-ford算法最核心的思想就是“松弛操作”,进行g.node_num-1轮松弛操作即可，原理和dijkstra类似。

非队列优化

1
2
3
4
5
6
7
8
9
10
11
12
13
void Bellman_Ford(Graph g,int origin, int dis[]) {
    for (int i = 1; i <= g.node_num; i++) {
        dis[i] = INF;
    }
    dis[origin] = 0;
    for (int k = 1; k <= g.node_num - 1; k++) {
        for (int i = 1; i <= g.edge_num; i++) {
            if (dis[g.e[i].to] > dis[g.e[i].from] + g.e[i].val) {
                dis[g.e[i].to] = dis[g.e[i].from] + g.e[i].val;
            }
        }
    }
}

队列优化

Bellman_ford算法的队列优化又被称为SPFA算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int book[M];  // judge node in que
void Bellman_Ford(Graph g, int origin, int dis[]) {
    queue<int> que;
    for (int i = 1; i <= g.node_num; i++) {
        dis[i] = INF;
    }
    dis[origin] = 0;
    que.push(origin);
    book[origin] = 1;
    while (!que.empty()) {
        int k = g.head[que.front()];//head->-1
        while (k != -1) {
            if (dis[g.e[k].to] > dis[g.e[k].from] + g.e[k].val) {
                dis[g.e[k].to] = dis[g.e[k].from] + g.e[k].val;
                if (!book[g.e[k].to]) {
                    que.push(g.e[k].to);
                    book[g.e[k].to] = 1;
                }
            }
            k = g.e[k].link;
        }
        book[que.front()] = 0;
        que.pop();
    }
}

算法对比

Floyd Dijkstra Bellman-Ford 队列优化的Bellman-Ford(SPFA)
空间复杂度 $O(N^2)$ $O(M)$ $O(M)$ $O(M)$
时间复杂度 $O(N^3)$ $O((M+N)logN)$ $O(NM)$ 最坏也是$O(NM)$
适用情况 稠密图
和顶点关系密切		 稠密图
和顶点关系密切		 稀疏图
和边关系密切		 稀疏图
和边关系密切
负权 可以解决负权 不能解决负权 可以解决负权 可以解决负权

Floyd 算法虽然总体时间复杂度高，但是可以解决负权边，并且均摊到每一点对上，在所有的算法中还是属于较优的。另外，Floyd 算法较小的编码复杂度也是它的一大优势。所以，如果要求的是所有点对间的最短路径，或者如果数据范围较小，则 Floyd 算法比较适合。

Diikstra算法最大的弊端是它无法适应有负权边的图。但是 Diikstra具有良好的可扩展性，扩展后可以适应很多问题。另外用堆优化的 Dijkstra 算法的时间复杂度可以达到 O(MlogN)。

当边有负权时，需要使用 Bellman-Ford算法或者队列优化的 Bellman-Ford算法。

因此我们选择最短路径算法时，要根据实际需求和每一种算法的特性，选择适合的算法。

tips：对于多源单终点的最短路径，可以通过求邻接矩阵的对称矩阵的方式求解。(即利用正向边和反向边各求一次最短路径即可)

相关题目链接：P1629 邮递员送信 - 洛谷

模板题

最长路

最长路

题目描述

设 $G$ 为有 $n$ 个顶点的带权有向无环图，$G$ 中各顶点的编号为 $1$ 到 $n$，请设计算法，计算图 $G$ 中 $1, n$ 间的最长路径。

输入格式

输入的第一行有两个整数，分别代表图的点数 $n$ 和边数 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行 $3$ 个整数 $u, v, w$（$u<v$），代表存在一条从 $u$ 到 $v$ 边权为 $w$ 的边。

输出格式

输出一行一个整数，代表 $1$ 到 $n$ 的最长路。

若 $1$ 无法到达 $n$，请输出 $-1$。

样例 #1

样例输入 #1

1
2
2 1
1 2 1

样例输出 #1

1
1

提示

【数据规模与约定】

  • 对于 $20%$的数据，$n \leq 100$，$m \leq 10^3$。
  • 对于 $40%$ 的数据，$n \leq 10^3$，$m \leq 10^{4}$。
  • 对于 $100%$ 的数据，$1 \leq n \leq 1500$，$0 \leq m \leq 5 \times 10^4$，$1 \leq u, v \leq n$，$-10^5 \leq w \leq 10^5$。

AC代码

其实这题由于存在负值，其实最长路就是最短路的负值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
#define M 100007
#define N 1007
#define INF 0x3f3f3f3f
#define ll long long
#define db double
typedef struct edge {
    int from, to, link;
    int id, val;
} Edge;
typedef struct node {
    int id;
} Node;
typedef struct graph {
    int head[N]; 
    int node_num = 0;
    Node p[N];
    int edge_num = 0;
    Edge e[M];
} Graph;
Graph g;
int dis[M];
void Bellman_Ford(Graph g, int dis[]) {
    for (int i = 1; i <= g.node_num; i++) {
        dis[i] = INF;
    }
    dis[1] = 0;
    for (int k = 1; k <= g.node_num - 1; k++) {
        for (int i = 1; i <= g.edge_num; i++) {
            if (dis[g.e[i].to] > dis[g.e[i].from] + g.e[i].val) {
                dis[g.e[i].to] = dis[g.e[i].from] + g.e[i].val;
            }
        }
    }
}
void add_edge(int from, int to, int value) {
    g.e[++g.edge_num].to = to;
    g.e[g.edge_num].from = from;
    g.e[g.edge_num].val = value;
}
int m;
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> g.node_num >> m;
    int u, v, w;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        add_edge(u, v, -1 * w);
    }
    Bellman_Ford(g, dis);
    int ans = -1;
    ans = max(ans, -1 * dis[g.node_num]);
    cout << ans << endl;
    return 0;
}
  • Title: shortest-path-algorithm
  • Author: Charles
  • Created at : 2023-01-05 11:06:11
  • Updated at : 2023-07-30 10:53:16
  • Link: https://charles2530.github.io/2023/01/05/shortest-path-algorithm/
  • License: This work is licensed under CC BY-NC-SA 4.0.
recommend_articles
P8 Design documents P8 Design documents database-theory-7 database-theory-7 Cpp_part8 Cpp_part8
recommend_articles
P8 Design documents P8 Design documents database-theory-7 database-theory-7
Comments
On this page
shortest-path-algorithm
  1. shortest-path-algorithm
    1. 最短路径算法
      1. 1.Floyd
        1. 算法思路
      2. 2.Dijkstra
        1. 算法思路
        2. Dijkstra的堆优化(后续补充部分)
      3. 3.Bellman-Ford
        1. 算法思路
        2. 非队列优化
        3. 队列优化
      4. 算法对比
    2. 模板题
      1. 题目描述
      2. 输入格式
      3. 输出格式
      4. 样例 #1
        1. 样例输出 #1
      5. 提示
      6. AC代码