最短路问题汇总

  • 最短路

    • 单源最短路

      • 求从一个点到其他所有点的最短距离
      • 所有边权是正数
        • 朴素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;
          }
          

热门相关:我的治愈系游戏   异世修真邪君   买妻种田:山野夫君,强势宠!   大妆   后福