最短路问题汇总

最短路

• 单源最短路

  • 求从一个点到其他所有点的最短距离

  • 所有边权是正数

    • 朴素Dijkstra算法 O(n^2)
      • 用于稠密图 m >= n
      • 步骤：
        • dist[i]：每个点离起点的距离
        • S：已经确定最短距离的点
        • V：没有确定最短距离的点
        • 初始化所有点的距离dist[起点] = 0；dist[其他点] = inf
        • 循环找V中离起点最近的点t
        • 将t放入S中
        • 用t的距离更新其他点的距离
      • 代码：

        const int N = 510;	
        int g[N][N];//稠密图用邻接矩阵
        int dist[N];//到原点的距离
        int st[N];//标记数组
        
        int dijkstra(){
        	//初始化距离
        	memset(d, 0x3f, sizeof d);
        	d[1] = 0;
        	
        	//遍历n次每次找距离原点最近的节点
        	for(int i = 1; i <= n; ++ i){
        		//在n个接节点中找
        		int t = 0;
        		for(int j = 1; j <= n; ++ j)
        			if(!st[j] && (!t || d[t] > d[j])
        				t = j; //找到了
        	}
        	
        	st[t] = 1; //标记已经找到最短距离
        	//更新所有节点的距离
        	for(int j = 1; j <= n; ++ j)
        		d[j] = min(d[j], d[t] + g[t][j]);
        	
        	if(d[n] == 0x3f3f3f3f) return -1;//1-n不连通
        	else return d[n]; //返回1-n的最短距离
        }
        
        //注意初始化边权为inf
        memset(g, 0x3f, sizeof g);
        //输入边权	
        while(m -- ){
        	int a, b, c;
        	cin >> a >> b >> c;
        	//有重边就取最小边权
        	g[a][b] = min(g[a][b], c);
        

    • 堆优化Dijkstra算法 O(mlogn)
      • 用于稀疏图 m <= n
      • 用堆存储每个节点的距离，堆顶元素就是离原点距离最近的节点
      • 代码：

        const int N = 1.5e5 + 10;
        typedef pair<int, int> PII;
        int st[N];
        int h[N], e[N], ne[N], idx = 1;
        int d[N], w[N];//w[i]边i的权值
        int n, m;
        
        void add(int x, int y, int z){
            e[idx] = y;
            ne[idx] = h[x];
            h[x] = idx;
            w[idx] = z;
            idx ++ ;
        }
        
        int dijkstra(){
            //初始化
            memset(d, 0x3f, sizeof d);
            d[1] = 0;
            
            priority_queue<PII, vector<PII>, greater<PII> > q;//小根堆
            
            q.push({0, 1});//起点入堆
            
            while(q.size()){
                auto t = q.top();//取堆顶元素，离起点最近的节点
                q.pop();
                
                int dist = t.first, node = t.second;//获取信息
                
                if(st[node]) continue;//已经求出最短距离就跳过
                st[node] = 1;
                
                for(int i = h[node]; i; i = ne[i]){
                    int j = e[i];//遍历相连的所有节点
                    if(d[j] > dist + w[i]){//更新最短距离
                        d[j] = dist + w[i];
                        q.push({d[j], j});//入堆
                    }
                        
                }
            }
            
            if(d[n] == 0x3f3f3f3f) return -1;
            else return d[n];
        }
        

  • 存在边权是负数

    • Bellman-Ford算法 O(nm)
      • 能够找到有边数限制的最短路径
      • 可以判断图中有无负权回路
        • 当外层循环执行n次（最短路更新了n次），说明最大有n条边构成了最短路，即有n+1个节点构成了最短路，根据鸽巢原理知，路中必有两个相同的节点，即路中有回路，又最短路更新的前提是最短路可以变得更小，所以该回路一定构成负权回路
      • 当有边数限制时，即使图中有负环也无所谓，因为负环不能被无限选择
      • 代码：

        const int N = 510;
        const int M = 1e4 + 10;
        
        struct egde{ //边
        	int u, v, w;
        }edges[M];
        int d[N], backup[N];//备份数组
        int n, m, k;
        
        int ballmen_ford(){
        	//初始化
        	memset(d, 0x3f, sizeof d);
        	d[1] = 0;
        	
        	for(int i = 1; i <= k; ++ i){ //k条边限制
        		memcpy(backup, d, sizeof d); //存备份
        		for(int j = 1; j <= m; ++ j){ //遍历每一条边
        			int u = edges[j].u; //获取信息
        			int v = edges[j].v;
        			int w = edges[j].w;
        			d[v] = min(d[v], backup[u] + w); //利用备份更新
        		}
        	}
        	
        	if(d[n] > 0x3f3f3f3f / 2) return -N;
        	else return d[n];
        }
        
        int main(){
        	cin >> n >> m >> k;
        	
        	for(int i = 1; i <= m; ++ i){
        		int x, y, z;
        		cin >> x >> y >> z;
        		edges[i] = {x, y, z};
        	}
        	
        	int t = ballmen_ford();
        	
        	if(t == -N) cout << "impossible";
        	else cout << t << endl;
        	return 0;
        }
        

    • SPFA算法 一般O(m)最坏O(nm)
      • 相当于优化版的ballmen_ford
      • 可以用于判断图中是否有负权回路
        • 设置cnt[i]数组，表示最短路从起点到i的边的数量，当某时刻边的数量>=n，说明路中有回路
        • 代码：

          const int N = 1e5 + 10;
          int h[N], e[N], ne[N], idx = 1;
          int d[N], w[N], cnt[N];//cnt[i]数组表示从起点到i的最短路中的边的数量
          int st[N]; //标记元素是否已经进入队列
          int n, m;
          
          void add(int a, int b, int z){
              e[idx] = b;
              ne[idx] = h[a];
              h[a] = idx;
              w[idx] = z;
              idx ++ ;
          }
          
          bool spfa(){
              queue<int> q;
              for(int i = 1; i <= n; ++ i){//所有节点入队，负环有可能不是从1-n路径上的，所以以每个节点为起点的路径都要检查
                  q.push(i);
                  st[i] = 1;//标记已入队
              }
              
              while(q.size()){
                  int t = q.front();
                  q.pop();
                  st[t] = 0;//出队
                  for(int i = h[t]; i; i = ne[i]){
                      int j = e[i];
                      if(d[j] > d[t] + w[i]){
                          d[j] = d[t] + w[i]; //更新
                          cnt[j] = cnt[t] + 1;//边数加一
                          if(cnt[j] >= n) return true;//边数>=n时，说明有环
                          if(!st[j]){
                              q.push(j);//只将更新过的元素入队
                              st[j] = 1;
                          }
                      }
                  }
              }
              return false;
          }
          
          int main(){
              cin >> n >> m;
              while(m -- ){
                  int x, y, z;
                  cin >> x >> y >> z;
                  add(x, y, z);
              }
              
              if(spfa()) cout << "Yes";
              else cout << "No";
              return 0;
          }
          

      • d[v] = min(d[v], backup[u] + w); //利用备份更新，这句话存在很多无效更新。只有当u更新过后，d[v]的更新才有效，因此只需要将更新过的节点放入一个集合，每次只用在集合中取元素去更新它邻接的节点
      • 有些正权图也可以用SPFA算法
      • 代码：

        const int N = 1e5 + 10;
        int h[N], e[N], ne[N], idx = 1;
        int d[N], w[N];
        int st[N]; //标记元素是否已经进入队列
        int n, m;
        
        void add(int a, int b, int z){
            e[idx] = b;
            ne[idx] = h[a];
            h[a] = idx;
            w[idx] = z;
            idx ++ ;
        }
        
        int spfa(){
        	//初始化
            memset(d, 0x3f, sizeof d);
            d[1] = 0;
            //队列存储更新过距离的节点
            queue<int> q;
            q.push(1);
            st[1] = 1;//标记已入队
            
            while(q.size()){//循环
                int t = q.front();
                q.pop();
                st[t] = 0;
                for(int i = h[t]; i; i = ne[i]){
                    int j = e[i];
                    if(d[j] > d[t] + w[i]){
                        d[j] = d[t] + w[i]; //更新
                        if(!st[j]){
                            q.push(j);//只将更新过的元素入队
                            st[j] = 1;
                        }
                    }
                }
            }
            if(d[n] > 0x3f3f3f3f / 2) return -N;
            else return d[n];
        }
        
        int main(){
            cin >> n >> m;
            while(m -- ){
                int x, y, z;
                cin >> x >> y >> z;
                add(x, y, z);
            }
            
            int t = spfa();
            if(t == -N) cout << "impossible";
            else cout << t;
            return 0;
        }
        

    • 存在负权边的图中存在最短路的话，图中一定不能有负权回路，除非最短路边数有限制，否则一直沿着回路绕，路径越来越小，直到最短路为负无穷

• 多源汇最短路

  • 源点起点，汇点终点，起点与终点任意选取
  • Floyd算法 O(n^3)
    • 可以处理有负权的图，但不能处理有负权回路的图
    • 代码：

      const int N = 210;
      const int M = 2e4 + 10;
      const int INF = 0x3f3f3f3f;
      int d[N][N];//存储两点间的最短路
      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;
          
      
          while(m -- ){
              int x, y, z;
              cin >> x >> y >> z;
              d[x][y] = min(d[x][y], z);//去重边
          }
          
          floyd();
          
          while(k -- ){
              int u, v;
              cin >> u >> v;
              int t = d[u][v];
              if(t > INF / 2) cout << "impossible" << endl;
              else cout << t << endl;
          }
          return 0;
      }