最短路算法分类

image.png

单源最短路

单源最短路,就是只有一个固定的起点。

无负权边

所有边中不存在负权边

朴素Dijkstra

dijkstra 是基于 贪心算法的,当存在负权边的时候,局部最优不能代表全局最优解

算法思想

  • 维护一个最短路集合st,每次选择未进入最短路集合中距离x点最短距离的点。
  • 把这个点加入最短路集合st中
  • 通过这个点来更新其他点到x点的最短路距离。

图解过程

  • dist[i]: 表示到点 x 的最短距离数组。一开始将dist距离设置无穷大。dist[x] = 0;
  • 以此图为例分析
    • image.png
    • 设x = 1,dist[1] = 0, st = [null]
    • image.png
    • 第一步
      • 从未在最短路集合中的st找到,距离点 1 最短的点
      • 找到 1 号点为 0
        • image.png
      • 把 1 号点加入 最短路集合 st = [1]
      • 通过 1 号点更新,与他相邻的点到 1 号点的最短路距离
        • image.png
    • 第二步
      • 从未在最短路集合中的st找到,距离点 1 最短的点
      • 找到 2 号点为 1
        • image.png
      • 把 2 号点加入 最短路集合 st = [1,2]
      • 通过 2 号点更新,与他相邻的点到 1 号点的最短路距离
        • image.png
    • 第三步
      • 从未在最短路集合中的st找到,距离点 1 最短的点
      • 找到 3 号点为 3
      • 把 3 号点加入 最短路集合 st = [1,2,3]
        • image.png
      • 因为没有相邻的点能通过3号点到达,所以操作结束。
        题目练习
  • image.png
  • 题目链接: Dijkstra求最短路 I
  • 思路分析:
    • 通过数据范围观察,m 远远大于 n,所以应该用邻接矩阵存储图,n的数据范围也不大
  • 题解代码
    • 
      	#include <iostream>
      	#include <algorithm>
      	#include <cstring>
      	using namespace std;
      
      	const int N = 505;
      	int g[N][N];
      	int n, m;
      	bool st[N];
      	int dist[N];
      
      	int dijkstra() {
      	    memset(dist, 0x3f, sizeof dist);
      	    dist[1] = 0;
      
      	    for (int i = 0; i < n; ++ i) {
      	        int t = -1;
      	        for (int j = 1; j <= n; ++ j) {
      	            if (!st[j] && (t == -1 || dist[t] > dist[j]))
      	                t = j;
      	        }
      
      	        st[t] = true;
      
      	        for (int j = 1; j <= n; ++ j)
      	            dist[j] = min(dist[j], dist[t] + g[t][j]);
      	    }
      
      	    if (dist[n] == 0x3f3f3f3f)
      	        return -1;
      	    return dist[n];
      	}
      
      	int main() {
      	    cin >> n >> m;
      	    memset(g, 0x3f, sizeof g);
      	    for (int i = 0; i < m; ++ i) {
      	        int x, y, c;
      	        cin >> x >> y >> c;
      	        if (x != y)
      	            g[x][y] = min(g[x][y], c);
      	    }
      
      	    int t = dijkstra();
      	    cout << t << endl;
      	    return 0;
      	}
      
堆优化Dijkstra

算法思想

  • 通过朴素版的dijkstra, 知道每次我们都需要找到当前最小且未加入最短路集合中的点。每次都要遍历所有点,这个操作太耗时。通过 小根堆这个数据结构,我们能很快的找到最小的点。
  • 优化的代码
    • 
      	let size = 0;
      	let heap = [];
      
      	let swap = (i, j) => {
      	    let tmp = heap[i];
      	    heap[i] = heap[j];
      	    heap[j] = tmp;
      	}
      
      	let insert = x => {
      	    heap[++size] = x;
      	    up(size);
      	}
      
      	let pop = () => {
      	    let x = heap[1];
      	    swap(1, size --);
      	    down(1);
      	    return x;
      	}
      
      	let down = u => {
      	    let t = u;
      	    if (u * 2 <= size && heap[u * 2][1] < heap[t][1])
      	        t = u * 2;
      	    if (u * 2 + 1 <= size && heap[u * 2 + 1][1] < heap[t][1])
      	        t = u * 2 + 1;
      	    if (t !== u) {
      	        swap(t, u);
      	        down(t);
      	    }
      
      	}
      
      	let up = u => {
      	    let t = Math.floor(u / 2);
      	    if (t && heap[t][1] > heap[u][1]) {
      	        swap(t, u);
      	        up(t);
      	    }
      	}
      
      	const N = 150010;
      	const h = new Int32Array(N).fill(-1),
      	      e = new Int32Array(N),
      	      w = new Int32Array(N),
      	      ne = new Int32Array(N);
      	let idx = 0;
      
      	function add(a, b, c) {
      	    e[idx] = b;
      	    w[idx] = c;
      	    ne[idx] = h[a];
      	    h[a] = idx ++;
      	}
      
      	function dijkstra() {
      	    const dis = new Int32Array(n + 1).fill(0x3f3f3f3f);
      	    const st = new Int32Array(n + 1);
      	    dis[1] = 0;
      	    insert([1, 0]);
      	    while (size !== 0) {
      	        let p = pop();
      	        let u = p[0];
      
      	        if (st[u])
      	            continue;
      	        st[u] = 1;
      	        for (let i = h[u]; i !== -1; i = ne[i]) {
      	            let j = e[i];
      	            // 只有被更新过的点,才有资格去更新其他点
      	            if (dis[j] > dis[u] + w[i]) {
      	                dis[j] = dis[u] + w[i];
      	                insert([j, dis[j]]);
      	            }
      	        }
      	    }
      	    if (dis[n] === 0x3f3f3f3f)
      	        return -1;
      	    return dis[n];
      	}
      
      	let n = 0, m = 0;
      	// 这里是读取数据
      	let buf = '';
      	process.stdin.on('readable', function () {
      	    let chunk = process.stdin.read();
      	    if (chunk) buf += chunk.toString();
      	});
      	let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
      	let getInputStr = line => line.split(' ').filter(s => s !== '');
      	process.stdin.on('end', function () {
      	    buf.split('\n').forEach(function (line, lineIdx) {
      	        if (lineIdx === 0) {
      	            n = getInputNums(line)[0];
      	            m = getInputNums(line)[1];
      	        } else if (lineIdx <= m) {
      	            let arr = getInputNums(line);
      	            let a = arr[0];
      	            let b = arr[1];
      	            let c = arr[2];
      	            add(a, b, c);
      	            if (lineIdx === m) {
      	                console.log(dijkstra());
      	            }
      	        }
      	    });
      	});
      
  • 上面的代码st表示的是 当前在堆中的点。此代码使用的是手写堆。使用的邻接表存储图
  • 题目链接:Dijkstra求最短路 II

有符权边

Bellman-Ford

当存在边权为负的时候使用

算法思想

  • 通过对边的松弛操作来渐进地降低从源结点 s 到每个结点 v 的最短距离。每次松弛操作,对所有边进行,每次都以上一个状态进行下一次松弛,避免串联反应。当某个点松弛n-1次后还能松弛,则说明该图存在负权回路。此算法子要能够遍历到所有边就可以,随意存储边。当求解有变数限制的时候,只能使用该算法
  • 图解过程
    • image.png

算法模板

  • 	    int n, m;       // n表示点数,m表示边数
      int dist[N];        // dist[x]存储1到x的最短路距离
    
      struct Edge     // 边,a表示出点,b表示入点,w表示边的权重
      {
          int a, b, w;
      }edges[M];
    
      // 求1到n的最短路距离,如果无法从1走到n,则返回-1。
      int bellman_ford()
      {
          memset(dist, 0x3f, sizeof dist);
          dist[1] = 0;
    
          // 如果第n次迭代仍然会松弛三角不等式,就说明存在一条长度是n+1的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路。
          for (int i = 0; i < n; i ++ )
          {
              for (int j = 0; j < m; j ++ )
              {
                  int a = edges[j].a, b = edges[j].b, w = edges[j].w;
                  if (dist[b] > dist[a] + w)
                      dist[b] = dist[a] + w;
              }
          }
    
          if (dist[n] > 0x3f3f3f3f / 2) return -1;
          return dist[n];
      }
    
      作者:yxc
      链接:https://www.acwing.com/blog/content/405/
      来源:AcWing
      著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    
  • 题目练习

    • image.png
    • 题目链接:有边数限制的最短路
    • 题解
      • 
        	#include <iostream>
        	#include <algorithm>
        	#include <cstring>
        	using namespace std;
        
        	const int N = 510, M = 1e4 + 10;
        
        	struct edge {
        	    int a, b, c;
        	}edges[M];
        
        	int n, m, k;
        	int dist[N];
        	int back[N];
        
        	int bellmanFord() {
        	    memset(dist, 0x3f, sizeof dist);
        	    dist[1] = 0;
        	    for (int i = 0; i < k; ++ i) {
        	        memcpy(back, dist, sizeof dist);
        	        for (int j = 0; j < m; ++ j) {
        	            int a = edges[j].a, b = edges[j].b, c = edges[j].c;
        	            dist[b] = min(dist[b], back[a] + c);
        	        }
        	    }
        
        
        	    return dist[n];
        	}
        
        	int main() {
        	    cin >> n >> m >> k;
        	    for (int i = 0; i < m; ++ i) {
        	        int a, b, c;
        	        cin >> a >> b >> c;
        	        if (a != b)
        	            edges[i] = {a,b,c};
        	    }
        
        	    int t = bellmanFord();
        	    if (t > 0x3f3f3f3f/2)
        	        puts("impossible");
        	    else
        	        cout << t << endl;
        	    return 0;
        
        	}
        
spfa 求最短路

是对 bellman-ford 一个优化

算法思想

  • 通过公式,dist[b] = min(dist[b], dist[a] + w) 得知,要让dist[b]变小,那么必然要dist[a] 变小的时候,才能变小。所以,我们通过维护变小的点的队列,来更新其他点,减少了bf算法中不必要的枚举。同时,spfa判断父权回路,通过维护一个count数组,count[i] 表示的是 一点到 i 点的最短路通过的路径数。当路径数大于等于 n 的时候就说明,图存在负权回路。为了避免代码冗余,需要维护一个st数组来统计,已经要入队列,准备更新其他边的点。

算法模板

  • spfa求最短路
    • 
      	int n;      // 总点数
      	int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
      	int dist[N];        // 存储每个点到1号点的最短距离
      	bool st[N];     // 存储每个点是否在队列中
      
      	// 求1号点到n号点的最短路距离,如果从1号点无法走到n号点则返回-1
      	int spfa()
      	{
      	    memset(dist, 0x3f, sizeof dist);
      	    dist[1] = 0;
      
      	    queue<int> q;
      	    q.push(1);
      	    st[1] = true;
      
      	    while (q.size())
      	    {
      	        auto t = q.front();
      	        q.pop();
      
      	        st[t] = false;
      
      	        for (int i = h[t]; i != -1; i = ne[i])
      	        {
      	            int j = e[i];
      	            if (dist[j] > dist[t] + w[i])
      	            {
      	                dist[j] = dist[t] + w[i];
      	                if (!st[j])     // 如果队列中已存在j,则不需要将j重复插入
      	                {
      	                    q.push(j);
      	                    st[j] = true;
      	                }
      	            }
      	        }
      	    }
      
      	    if (dist[n] == 0x3f3f3f3f) return -1;
      	    return dist[n];
      	}
      
      
  • spfa判断负权回路
    • 
      	int n;      // 总点数
      	int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
      	int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离,cnt[x]存储1到x的最短路中经过的点数
      	bool st[N];     // 存储每个点是否在队列中
      
      	// 如果存在负环,则返回true,否则返回false。
      	bool spfa()
      	{
      	    // 不需要初始化dist数组
      	    // 原理:如果某条最短路径上有n个点(除了自己),那么加上自己之后一共有n+1个点,由抽屉原理一定有两个点相同,所以存在环。
      
      	    queue<int> q;
      	    for (int i = 1; i <= n; i ++ )
      	    {
      	        q.push(i);
      	        st[i] = true;
      	    }
      
      	    while (q.size())
      	    {
      	        auto t = q.front();
      	        q.pop();
      
      	        st[t] = false;
      
      	        for (int i = h[t]; i != -1; i = ne[i])
      	        {
      	            int j = e[i];
      	            if (dist[j] > dist[t] + w[i])
      	            {
      	                dist[j] = dist[t] + w[i];
      	                cnt[j] = cnt[t] + 1;
      	                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点(不包括自己),则说明存在环
      	                if (!st[j])
      	                {
      	                    q.push(j);
      	                    st[j] = true;
      	                }
      	            }
      	        }
      	    }
      
      	    return false;
      	}
      
      
      

题目练习

  • spfa求最短路

    • image.png
    • 题目链接:spfa求最短路
    • 算法思路:根据题目的数据范围可以看出是个稀疏图,应该用邻接表存储。因为存在负权变,要求最短路,可选择spfa,或bellman-ford, 看数据范围O(nm)时间复杂度太高,所以选择spfa 时间复杂度 O(mlogn);
    • 解题代码:
      • 
        	#include <iostream>
        	#include <algorithm>
        	#include <cstring>
        	#include <queue>
        	using namespace std;
        
        	const int N = 1e5 + 10;
        	int h[N], e[N], w[N], ne[N], idx;
        	int dist[N];
        	bool st[N];
        	queue<int> q;
        	int n, m;
        	void add(int a, int b, int c) {
        	    e[idx] = b;
        	    w[idx] = c;
        	    ne[idx] = h[a];
        	    h[a] = idx ++;
        	}
        
        	int spfa() {
        	    memset(dist, 0x3f, sizeof dist);
        	    dist[1] = 0;
        	    st[1] = true;
        	    q.push(1);
        	    while(q.size()) {
        	        int u = q.front();
        	        q.pop();
        
        	        st[u] = false;
        
        	        for (int i = h[u]; i != -1; i = ne[i]) {
        	            int j = e[i];
        	            if (dist[j] > dist[u] + w[i]) {
        	                dist[j] = dist[u] + w[i];
        
        	                if (!st[j]) {
        	                    st[j] = true;
        	                    q.push(j);
        	                }
        	            }
        	        }
        	    }
        
        	    return dist[n];
        	}
        
        	int main() {
        	    memset(h, -1, sizeof h);
        	    cin >> n >> m;
        	    for (int i = 0; i < m; ++ i) {
        	        int a, b, c;
        	        cin >> a >> b >> c;
        	        add(a, b, c);
        	    }
        
        	    int t = spfa();
        	    if (t == 0x3f3f3f3f)
        	        cout << "impossible" << endl;
        	    else
        	        cout << t << endl;
        	    return 0;
        	}
        
  • spfa 判断负权回路

    • image.png
    • 题目链接:spfa判断负环
    • 解题思路:
      • 通过bellman-ford 可以知道,当一个点被松弛n此之后,就必然会存在负权回路。我们用一个count数组,来维护一点到该点的最短路通过的路径数目。
    • 解题代码:
      • 				#include <iostream>
        	#include <algorithm>
        	#include <cstring>
        	#include <queue>
        
        	using namespace std;
        
        	const int N = 2010, M = 1e4 + 10;
        	int h[N], e[M], ne[M], w[M], idx;
        	bool st[N];
        	int dist[N];
        	int cnt[N];
        	int n, m;
        	queue<int> q;
        
        	void add(int a, int b, int c) {
        	    e[idx] = b;
        	    w[idx] = c;
        	    ne[idx] = h[a];
        	    h[a] = idx ++;
        	}
        
        	bool spfa() {
        	    // 因为负权回路不一定在一个图上,因为图可能有部分没有连接的变,是两个没有关系的集合
        	    for (int i = 1; i <= n; ++ i) {
        	        st[i] = true;
        	        q.push(i);
        	    }
        
        	    while(q.size()) {
        	        int u = q.front();
        	        q.pop();
        
        	        st[u] = false;
        
        	        for (int i = h[u]; i != -1; i = ne[i]) {
        	            int j = e[i];
        	            if (dist[j] > dist[u] + w[i]) {
        	                dist[j] = dist[u] + w[i];
        	                cnt[j] = cnt[u] + 1;
        	                if (cnt[j] >= n) {
        	                    return true;
        	                }
        	                if (!st[j]) {
        	                    st[j] = true;
        	                    q.push(j);
        	                }
        	            }
        	        }
        	    }
        	    return false;
        	}
        
        	int main() {
        	    memset(h, -1, sizeof h);
        	    cin >> n >> m;
        	    for (int i = 0; i < m; ++ i) {
        	        int a, b, c;
        	        cin >> a >> b >> c;
        	        add(a, b, c);
        	    }
        
        	    bool t = spfa();
        	    cout << (t ? "Yes":"No") << endl;
        	    return 0;
        	}
        
        

多源汇最短路

给多个起点,要求得出到某些点的最短路距离

Floyd

算法思想

  • 基于动态规划,设d[k][i][j], 表示从i出发通过1~k这些点得到i点到j点的最短路。可以得出动态规划公式 d[k][i][j] = min(d[k - 1][i][k] + d[k - 1][k][j], d[k][i][j]) <=> d[i][j] = min(d[i][k] + d[k][j], d[i][j]);
    算法模板
  • 
    	初始化:
    	    for (int i = 1; i <= n; i ++ )
    	        for (int j = 1; j <= n; j ++ )
    	            if (i == j) d[i][j] = 0;
    	            else d[i][j] = INF;
    
    	// 算法结束后,d[a][b]表示a到b的最短距离
    	void floyd()
    	{
    	    for (int k = 1; k <= n; k ++ )
    	        for (int i = 1; i <= n; i ++ )
    	            for (int j = 1; j <= n; j ++ )
    	                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    	}
    
    
    

题目练习

  • image.png
  • 题目链接:Floyd求最短路
  • 题目分析:通过题目可以看出,要查询k次x点到y点的最短路距离,属于多源汇最短路问题,所以因该使用Floyd求解
  • 解题代码:
    • 
      	#include <iostream>
      	#include <algorithm>
      	#include <cstring>
      	using namespace std;
      
      	const int N = 210;
      	int d[N][N];
      	const int INF = 0x3f3f3f3f;
      
      	int n, m, k;
      
      	void floyd() {
      	    for (int k = 1; k <= n; ++ k) {
      	        for (int i = 1; i <= n; ++ i) {
      	            for (int j = 1; j <= n; ++ j)
      	                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      	        }
      	    }
      	}
      
      	int main() {
      	    cin >> n >> m >> k;
      
      	    for (int i = 1; i <= n; ++ i) {
      	        for (int j = 1; j <= n; ++ j) {
      	            if (i == j) d[i][j] = 0;
      	            else d[i][j] = INF;
      	        }
      	    }
      
      	    for (int i = 0; i < m; ++ i) {
      	        int a, b, c;
      	        cin >> a >> b >> c;
      	        d[a][b] = min(d[a][b], c);
      	    }
      
      	    floyd();
      
      	    while(k --) {
      	        int x, y;
      	        cin >> x >> y;
      	        int t = d[x][y];
      
      	        if (t > INF/2)
      	            cout << "impossible" << endl;
      	        else
      	            cout << t << endl;
      
      	    }
      	    return 0;
      	}