单源最短路和最长路总结

yuanheci 2023年02月27日 458次浏览

单源最短路和最长路一共可分为：
(1)(1) 加法最短路
(2)(2) 加法最长路
(3)(3) 乘法最短路
(4)(4) 乘法最长路

下面就一一来分析一下~

1、 加法最短路

最基础的情况，用经典的单源最短路算法都可以求解。

2、 加法最长

可以用spfa；
当满足图中边权全为负数时，可以用dij。

3、 乘法最短路

可以用spfa；
当所有边权均满足w[i] >= 1时，可以用dij。

4、乘法最长路

可以用spfa；
当所有边权均满足0 < w[i] < 1时，可以用dij。

小结：关于dij在加法中，经典dij可在全负权边图中跑最长路、全正权边图中跑最短路。

分析方式总结

  套用最短路和最长路原理来分析，SPFA的正确性是基于它的松弛操作，所以自然是可以求乘积最小值和乘积最大值的。
  考虑Dij为什么不一定行，因为Dij的最短路算法是贪心的，它贪心的选最小的并且认为这个点不会被更新了，为什么不会被更新了？因为没有负权边，从而你加入优先队列里的dis只会越来越大，毕竟一个数+一个正数一定变大，不可能以后取出来某一个点更新这个点，故我这个点取出来了，就不会再使用。Dij的正确性是基于 “放入优先队列的点的dis是单调的” 这一条件。所以对于求最短路，我们要求dis单调递增，即不存在负权边，对于最大乘积，我们要求乘积只允许单调变小，即乘的在(0,1)之间，对于最小乘积，我们要求乘积必须单调变大，即所有边权都是>=1的。（似乎也不用严格单调，只要不增不减就行了）。

另外注意如果用Dij求最长路(加法/乘法)，那么记得要用大根堆。

例题

最小花费

朴素Dij做法

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. using namespace std;

  6. const int N = 2010;
  7. int n, m;
  8. double w[N][N];
  9. double dist[N];   //0表示不相连 
  10. int S, T;
  11. bool st[N];

  13. void dijkstra(){
  14.     dist[S] = 1;   //乘法的零元是1
  15.     for(int i = 1; i < n; i++){
  16.         int t = -1;
  17.         for(int j = 1; j <= n; j++){
  18.             if(!st[j] && (t == -1 || dist[j] > dist[t]))
  19.                  t = j;
  20.         }
  21.         st[t] = true;
  22.         for(int k = 1; k <= n; k++)
  23.             if(dist[k] < dist[t] * w[t][k])
  24.                 dist[k] = dist[t] * w[t][k];
  25.     }
  26. }

  28. int main(){
  29.     scanf("%d%d", &n, &m);

  31.     for(int i = 1; i <= m; i++){
  32.         int x, y, z;
  33.         scanf("%d%d%d", &x, &y, &z);
  34.         w[x][y] = w[y][x] = (100 - z) / 100.0;
  35.     }
  36.     scanf("%d%d", &S, &T);

  38.     dijkstra();
  39.     printf("%.8f\n", 100 / dist[T]);

  41.     return 0;
  42. }

堆优化版本dij

  1. #include <bits/stdc++.h>
  2. using namespace std;

  4. #define x first
  5. #define y second
  6. typedef pair<double, int> PDI;
  7. const int N = 2010, M = 200010;
  8. int h[N], e[M], ne[M], idx;
  9. double w[M], dist[N];
  10. bool st[N];
  11. int n, m;
  12. int start, ed;

  14. void add(int a, int b, double c){
  15.     e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
  16. }

  18. void dijkstra(){
  19.     priority_queue<PDI, vector<PDI>> heap;  //大根堆
  20.     dist[start] = 1;
  21.     heap.push({1, start});  //乘法的零元是1
  22.     while(heap.size()){
  23.         auto t = heap.top();
  24.         heap.pop();
  25.         int ver = t.y;
  26.         double dis = t.x;
  27.         if(st[ver]) continue;
  28.         st[ver] = true;
  29.         for(int i = h[ver]; ~i; i = ne[i]){
  30.             int j = e[i];
  31.             if(dist[j] < dis * w[i]){
  32.                 dist[j] = dis * w[i];
  33.                 heap.push({dist[j], j});
  34.             }
  35.         }
  36.     }
  37. }

  39. void solve(){
  40.     scanf("%d%d", &n, &m);
  41.     memset(h, -1, sizeof h);
  42.     while(m -- ){
  43.         int a, b, c;
  44.         scanf("%d%d%d", &a, &b, &c);
  45.         add(a, b, (100 - c) / 100.0), add(b, a, (100 - c) / 100.0);
  46.     }
  47.     scanf("%d%d", &start, &ed);
  48.     dijkstra();
  49.     printf("%.8lf\n", 100.0 / dist[ed]);
  50. }

  52. int main(){
  53.     int T = 1;
  54.     // scanf("%d", &T);
  55.     while(T -- ){
  56.         solve();
  57.     }

  59.     return 0;
  60. }

spfa做法

  1. #include <bits/stdc++.h>
  2. using namespace std;

  4. const int N = 2010, M = 200010;
  5. int h[N], e[M], ne[M], idx;
  6. double w[M];
  7. double dist[N];
  8. bool st[N];
  9. int q[N], hh, tt;
  10. int n, m, start, ed;

  12. void add(int a, int b, double c){
  13.     e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
  14. }

  16. void spfa(){
  17.     dist[start] = 1;  //乘法的零元是1
  18.     st[start] = true;
  19.     hh = 0, tt = 0;
  20.     q[tt++] = start;
  21.     while(hh != tt){
  22.         int t = q[hh++];
  23.         if(hh == N) hh = 0;
  24.         st[t] = false;
  25.         for(int i = h[t]; ~i; i = ne[i]){
  26.             int j = e[i];
  27.             if(dist[j] < dist[t] * w[i]){
  28.                 dist[j] = dist[t] * w[i];
  29.                 if(!st[j]){
  30.                     st[j] = true;
  31.                     q[tt++] = j;
  32.                     if(tt == N) tt = 0;
  33.                 }
  34.             }
  35.         }
  36.     }
  37. }

  39. int main(){
  40.     scanf("%d%d", &n, &m);
  41.     memset(h, -1, sizeof h);
  42.     for(int i = 0; i < m; i++){
  43.         int a, b, c;
  44.         scanf("%d%d%d", &a, &b, &c);
  45.         add(a, b, 1.0 - 1.0 * c / 100);
  46.         add(b, a, 1.0 - 1.0 * c / 100);
  47.     }
  48.     scanf("%d%d", &start, &ed);
  49.     spfa();
  50.     printf("%.8lf\n", 100.0 / dist[ed]);

  52.     return 0;
  53. }
上一篇： 括号序列的性质总结