本文共 5057 字，大约阅读时间需要 16 分钟。

最短路 :

关键点 : 建图 ( 算法的实现 )

m ~ n 稀疏图 m ~ n^2 稠密图

只用考虑有向图 , 无向图就是在有向图的基础上加 1 条边

单源最短路 :

所有边权都是正数 :

朴素的 Dijkstra 算法 :

思想 : 贪心 .

求 1 号点 到其他所有的点的距离

集合 s : 当前已经确定最短距离的点

步骤 :

1. dis[1] = 0 其他所有的点 dis[i] = 正无穷或一个很大的值

2. for (int i = 1;i <= n;i ++ ) 1 ~ n

   1. 找到 t --> 不在 s 中的距离最近的点
   2. 将 t 加入到集合 s 中去
   3. 用 t 来更新其他所有点的距离 从t出去的所有边能不能更新其他所有点的距离 dis[x] > dis[t] + w

   模版 :

   代码如下 :

   // 朴素的 Dijkstra 算法 : // 贪心// 先设置起点的距离为 0 -- dist[1] = 0 ; 其他点的距离设置为无穷大// 边数很多 , 稠密图 , 用邻接矩阵存储// ex : 给定一个 n个点m条边的有向图 , 图中可能存在重边和自环 , 所有边权均为正值// 求出 1 号点 到其余 n 号点的距离 , 如果不能走到 , 则输出 -1 ;#include 
        
         #include 
         
          #include 
          
           using namespace std ;const int N = 510 ;int n , m ;int dist[N] ; int g[N][N] ;bool st[N] ;int dijkstra(){
   
           
    memset(dist,0x3f,sizeof dist) ;
           
   dist[1] = 0 ;
           
   // n 次迭代
           
   for(int i = 0;i < n;i ++ )
           
   {
   
           
    int t = -1 ;
           
   // 找到当前距离 起始点最短的点 t , 并将其加入集合 s 中
           
   for(int j = 1;j <= n;j ++ )
           
   {
   
           
    if(!st[j] && (t == -1 || dist[j] < dist[t]))
           
   {
   
           
    t = j ;
           
   }
           
   }
           
   // 将当前距离起始点最短的点 t 加入集合 s 中
           
   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 ;
           
   else return dist[n] ;}int main(){
   
           
    scanf("%d%d",&n,&m) ;
           
   memset(g,0x3f,sizeof g) ;
           
   while (m --)
           
   {
   
           
    int a, b , c ;
           
   scanf("%d%d%d",&a,&b,&c) ;
           
   g[a][b] = min(g[a][b],c) ;
           
   }
           
   int x = dijkstra() ;
           
   printf("%d \n",x) ;
           
   return 0 ;}
          
         
        

堆优化版的 Dijkstra 算法 :

使用 c++ 中 STL 的优先队列来存储 dist , 优化后时间复杂度为 mlog n .

代码如下 :

// 稀疏图 , 用邻接表存储// 不需要手写堆 , 直接用 c++ 中的 STL 即可 , priority_queue ;  dist 用堆存储// 注 : 优先队列不支持修改任意一个元素的操作#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std ;typedef pair
       
         PII ;const int N = 1010 ;int n , m ;// 邻接表存储int h[N] , w[N] , e[N] , ne[N] , idx ;int dist[N] ; bool st[N] ;void add(int a,int b,int c){

        
   e[idx] = b ; w[idx] = c ; ne[idx] = h[a] ; h[a] = idx ++ ;}int dijkstra(){

        
   memset(dist,0x3f,sizeof dist) ;
        
dist[1] = 0 ;
        
priority_queue
        
         
          ,greater
          
           > heap ;
           
heap.push({    0,1}) ; // 将一号点放入堆中 , 更新其他所有点 距离为0 编号为1
           
while (heap.size()) // 相当于当所有点的最短距离都被找到,就终止循环
           
{ 
           
   auto t = heap.top() ;
           
heap.pop() ;
           
int ver = t.second , distance = t.first ;
           
if(st[ver]) continue ;  // 去除容于的情况 , 就是一个点的两个dist是最小的两个值,此时这个点会被更新两次,实际更新一次即可
           
for(int i = h[ver] ; i != -1;i = ne[i])
           
{ 
           
   int j = e[i] ;
           
if(dist[j] > distance + w[i])
           
{ 
           
   dist[j] = distance + w[i] ;
           
heap.push({    dist[j],j}) ; // 更新距离
           
}
           
}
           
}
           
if(dist[n] == 0x3f3f3f3f) return -1 ;
           
else return dist[n] ;}int main(){ 
           
   scanf("%d%d",&n,&m) ;
           
// 邻接表的初始化 , 表头置空 -- 赋值为-1
           
memset(h,-1,sizeof h) ;
           
while (m -- )
           
{ 
           
   int a , b , c ; scanf("%d%d%d",&a,&b,&c) ;
           
add(a,b,c) ;
           
}
           
int t = dijkstra() ;
           
printf("%d \n",t) ;
           
return 0 ;}
          
         
        
       
      
     
    
   

存在负权边 :

Bellman – Ford 算法 :

两重循环 , 时间复杂度较高 , 一般较少用来判断负环 , 一般用SPFA算法来判断负环

n 次迭代 for n次

每一次循环所有边 a,b,c a–>b 权重为 w

可以用结构体存储每一条边 m条边 , 开一个大小为 m 的数组即可

struct {

   int a , b , w ; }edge[m] ;

循环完后最短距离满足三角不等式 : dist[b] <= dist[a] + w

更新的过程被称为 松弛 操作 : dist[b] = min(dist[b],dist[a] + w)

如果存在最短路 , 则图中不包含负权回路

模版如下 :

给定一个n个点m条边的有向图 , 图中可能存在重边和自环,边权可能为负数

请求出从1号点到n号点的最多经过k条边的最短距离.如果无法从1号点到n号点,输出impossible

注意 : 图中可能存在负权回路

有边数限制的最短路,只能用bellman-ford算法.

memcoy函数 : 逐字节复制

backup : 备份数组 , 防止串联现象的发生 , 也就是用上一次迭代的结果来进行更新

代码如下 :

// Bellman-Ford 算法 :// 题目://给定一个n个点m条边的有向图 , 图中可能存在重边和自环,边权可能为负数//请求出从1号点到n号点的最多经过k条边的最短距离.如果无法从1号点到n号点,输出impossible//注意 : 图中可能存在负权回路#include 
   
    #include 
    
     #include 
     
      using namespace std ;const int N = 510 , M = 10010 ;int n , m , k ; int dist[N] , backup[N] ;struct Edge{

      
   int a , b , w ;}edges[M] ;int bellman_ford(){

      
   memset(dist,0x3f,sizeof(dist)) ;
      
dist[1] = 0 ;
      
for(int i = 0;i < k;i ++ )
      
{

      
   memcpy(backup,dist,sizeof dist) ; // 将dist数组逐字节复制给backup数组
      
// 备份 , 防止串联结果出现 (因为边数有限制)
      
for(int j = 0;j < m;j ++ )
      
{

      
   int a = edges[j].a , b = edges[j].b , w = edges[j].w ;
      
dist[b] = min(dist[b] , backup[a] + w) ;
      
}
      
}
      
if(dist[n] > 0x3f3f3f3f / 2 ) return -1 ; // 因为存在负边 , 所以最大值距离被更新后会小于最大值 , 这里就要将最大值除以2以防止其越界
      
else return dist[n] ;}int main(){

      
   scanf("%d%d%d",&n,&m,&k) ; // k 为最大经过的边数
      
for(int i = 0;i < m;i ++ )
      
{

      
   int a , b , w ;
      
scanf("%d%d%d",&a,&b,&w) ;
      
edges[i] = {
   a , b , w} ; // 会按结构体变量的声明顺序进行赋值
      
}
      
int t = bellman_ford() ;
      
if(t == -1) puts("impossible") ;
      
else printf("%d\n",t) ;
      
return 0 ;}
     
    
   

SPFA 算法 :

大部分最短路问题都没有负环

一定要求图中不含负环 , 区别于 bellman-ford算法

原理 : bfs 队列 queue

代码如下 :

多源汇最短路 :

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])

先循环 k , i 和 j 的顺序可以进行颠倒

注意 : 这里循环的顺序不能调换 , 具体理解为 先遍历图中所有的点 , 再将这些点与其他所有的点进行松弛操作进行比较

转载地址：https://blog.csdn.net/weixin_45877540/article/details/108809382 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！