各种最短路径算法
发布日期:2022-02-24 01:06:48 浏览次数:1 分类:技术文章

本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:vue + Element上传多个文件,支持删除重新上传,上传后将后台返回的URL发送给后台存到数据库
下一篇:图 . 树 . bfs . dfs .

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.36.149.24]2022年06月21日 13时47分35秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章