算法小讲堂之最短路算法(Floyd+bellman+SPFA+Dijkstra)

前言

如果你对图论相关知识一点也没有，那么建议您先去了解这些知识：https://acmer.blog.csdn.net/article/details/122310835，然后就可以快乐的学习最短路算法啦

视频中绘图软件：https://csacademy.com/app/graph_editor/

配套讲解视频：https://www.bilibili.com/video/BV1Fa411C7wX/

如果哪里讲的有问题欢迎在评论区指出，感谢支持！

一、Floyd算法 1.1简介

Floyd算法算是最简单的算法，没有之一。适用于任何图

不管有向无向，边权正负，但是最短路必须存在。

基于动态规划的思想

1.2复杂度 1.2.1时间复杂度

O ( N 3 ) O(N^3) O(N3)

1.2.2空间复杂度

O ( N 2 ) O(N^2) O(N2)

1.3优缺点 1.3.1优点

常数小，容易实现，思路简单，能处理大部分图

1.3.2缺点

复杂度较高、不能处理负环图

1.4算法原理

我们定义一个三维数组 f [ k ] [ u ] [ v ] f[k][u][v] f[k][u][v]表示的是允许经过 [ 1 , k ] [1,k] [1,k]的点的 u u u到 v v v的最小距离，换句话说从 1 1 1到 k k k这些点可以作为 u u u到 v v v的中间节点，当然没也可以不经过，很显然我们如果要求解 u u u到 v v v的最小距离那么就是 f [ n ] [ u ] [ v ] f[n][u][v] f[n][u][v]（假设当前的图中有n个点的话），那么我们考虑怎么来维护这个关系呢，首先初始化来说， f [ 0 ] [ u ] [ v ] f[0][u][v] f[0][u][v]先初始化为INF，如果有边连接的话，那么我们取一个min就好，还有就是如果u和v相等的话应该初始化为0，那么我们就能推出这个状态是如何转移的：

f [ k ] [ u ] [ v ] = m i n ( f [ k − 1 ] [ u ] [ v ] , f [ k − 1 ] [ u ] [ k ] + f [ k − 1 ] [ k ] [ v ] ) f[k][u][v] = min(f[k-1][u][v],f[k-1][u][k] + f[k-1][k][v]) f[k][u][v]=min(f[k−1][u][v],f[k−1][u][k]+f[k−1][k][v])

我们对经过k点和不经过k点去一个min，那么我们的状态转移方程就构造好啦，下面给出代码

void Floyd(){
    for(int k = 1;k w;
		f[u][v] = min(f[u][v],w);
	}
	Floyd();
	while(k--){
		cin>>u>>v;
		if(f[u][v] > INF / 2) cout>t;
	int u,v,w;
	for(int i = 1;i >u>>v>>w;
		E.push_back({u,v,w});
		E.push_back({v,u,w});
	}
		
	bellman_ford(s);
	if(dis[t] >= INF / 2) coutw;
		E[i]={u,v,w};
	}
	bool k = bellman_ford();
	if(k) couts>>t;
	int u,v,w;
	for(int i = 1;i >u>>v>>w;
		E[u].push_back({v,w});
		E[v].push_back({u,w});
	}
	
	SPFA(s);
	if(dis[t] >= INF / 2) coutx->y->u 
         
        
      s−>x−>y−>u，其中y为 
       
        
         
         
           s 
          
         
           − 
          
         
           > 
          
         
           u 
          
         
        
          s->u 
         
        
      s−>u路径上第一个属于 
       
        
         
         
           T 
          
         
        
          T 
         
        
      T集合的点，而 
       
        
         
         
           x 
          
         
        
          x 
         
        
      x为 
       
        
         
         
           y 
          
         
        
          y 
         
        
      y的前驱节点（显然x∈S）。需要注意的是，可能存在 
       
        
         
         
           s 
          
         
           = 
          
         
           x 
          
         
        
          s=x 
         
        
      s=x或者 
       
        
         
         
           y 
          
         
           = 
          
         
           u 
          
         
        
          y=u 
         
        
      y=u的情况，即 
       
        
         
         
           s 
          
         
           − 
          
         
           > 
          
         
           x 
          
         
        
          s->x 
         
        
      s−>x或者 
       
        
         
         
           y 
          
         
           − 
          
         
           > 
          
         
           u 
          
         
        
          y->u 
         
        
      y−>u是一个不存在的路径
 
 
因为在 
       
        
         
         
           u 
          
         
        
          u 
         
        
      u结点之前加入的结点都满足 
       
        
         
         
           D 
          
         
           ( 
          
         
           u 
          
         
           ) 
          
         
           = 
          
         
           d 
          
         
           i 
          
         
           s 
          
         
           ( 
          
         
           u 
          
         
           ) 
          
         
        
          D(u)=dis(u) 
         
        
      D(u)=dis(u)，所以在 
       
        
         
         
           x 
          
         
        
          x 
         
        
      x点加入到 
       
        
         
         
           S 
          
         
        
          S 
         
        
      S集合时，有 
       
        
         
         
           D 
          
         
           ( 
          
         
           u 
          
         
           ) 
          
         
           = 
          
         
           d 
          
         
           i 
          
         
           s 
          
         
           ( 
          
         
           u 
          
         
           ) 
          
         
        
          D(u)=dis(u) 
         
        
      D(u)=dis(u)，此时边 
       
        
         
         
           ( 
          
         
           x 
          
         
           , 
          
         
           y 
          
         
           ) 
          
         
        
          (x,y) 
         
        
      (x,y)会被松弛，从而可以证明，将 
       
        
         
         
           u 
          
         
        
          u 
         
        
      u加入到 
       
        
         
         
           S 
          
         
        
          S 
         
        
      S时，一定有 
       
        
         
         
           D 
          
         
           ( 
          
         
           y 
          
         
           ) 
          
         
           = 
          
         
           d 
          
         
           i 
          
         
           s 
          
         
           ( 
          
         
           y 
          
         
           ) 
          
         
        
          D(y)=dis(y) 
         
        
      D(y)=dis(y)。
 
 
下面证明 
       
        
         
         
           D 
          
         
           ( 
          
         
           u 
          
         
           ) 
          
         
           = 
          
         
           d 
          
         
           i 
          
         
           s 
          
         
           ( 
          
         
           u 
          
         
           ) 
          
         
        
          D(u)=dis(u) 
         
        
      D(u)=dis(u)成立。在路径 
       
        
         
         
           s 
          
         
           − 
          
         
           > 
          
         
           x 
          
         
           − 
          
         
           > 
          
         
           y 
          
         
           − 
          
         
           > 
          
         
           u 
          
         
        
          s->x->y->u 
         
        
      s−>x−>y−>u中，因为图上所有边边权非负，因此 
       
        
         
         
           D 
          
         
           ( 
          
         
           y 
          
         
           ) 
          
         
           < 
          
         
           = 
          
         
           D 
          
         
           ( 
          
         
           u 
          
         
           ) 
          
         
        
          D(y)>v>>w;
		E[u].push_back({v,w});
        E[v].push_back({u,w});
	}
	DJ(s);
	if(dis[t] == INF) cout