精华内容
下载资源
问答
  • 最短路径问题
    万次阅读 多人点赞
    2021-05-12 13:56:18

    转载自:最短路径问题

    问题介绍

    简单地说,就是给定一组点,给定每个点间的距离,求出点之间的最短路径

    路径问题大概有以下几种:

    • 确定起点的最短路径问题:已知起始点,求起点到其他任意点最短路径的问题。即单源最短路径问题。

    • 确定终点的最短路径问题:与确定起点的问题相反,该问题是已知终点,求最短路径的问题。在无向图(即点之间的路径没有方向的区别)中该问题与确定起点的问题完全等同,在有向图(路径间有确定的方向)中该问题等同于把所有路径方向反转的确定起点的问题。

    • 确定起点终点的最短路径问题:已知起点和终点,求任意两点之间的最短路径。即多源最短路径问题。 

     

    我们先说明如何输入一个图,并以此为例:

                                  Image

    我们通过这样的形式输入数据:
    5 8 
    1 2 2 
    1 5 10 
    2 3 3
    2 5 7 
    3 1 4 
    3 4 4 
    4 5 5 
    5 3 3

    其中,第一行表示共有5个点(可以理解为城市),8条边(理解为路)。

    注意,这里一行的三个数据分别表示i点,j点,和从i到j的单向距离!单向!单向!

    我们直接输出最短路程。(也可以加上标记输出路径) 

    在具体解决问题之前,我们先要把这些数据存储起来,方便调用。这里我们直接用一个二维数组来模拟这个图(它的名字叫邻接矩阵):

    在图中,第i列第j行表示的是i到j的距离。其中,将到自己的距离定义为0,用无穷定义没有路径连通。存储到数组中,可以通过二维数组表示。

    下面我们就开始分别讲解几种解决最短路径问题的经典算法。

     

    1、深度优先遍历(DFS)

      我们知道,深度优先搜索常用于走迷宫,是一种遍历全图的暴力方法。同理,我们利用深度优先遍历,也是通过暴力遍历全图的方法来找到最短路径。因为我们可以在输入数据时对城市进行编号,所以我们将问题的描述改为求从1号城市到5号城市的最短路径长度 。(即初始城市到最后的城市)

      我们通过DFS递归函数,从起始1号城市起,不断地判断是否可以通过一个城市到达最后的5号城市(在回溯中判断),然后记录最小路程,不断更新。

    //DFS解最短路径问题 
    
    #include <iostream>
    using namespace std;
     
    const int INF=99999999;//正无穷
    int minn=INF;
    int n,dist[105][105],book[105];
     
    void dfs(int cur,int dis)
    {
        int j;
        //一点点优化:如果本次查找的路径到此已经超过前面查找的最短路径总长,就不需要再继续了
        if(dis>minn)
            return;
        if(cur==n)//到达要查的城市 
        {
            minn=min(dis,minn);
            return;
        }
     
        for(j=1;j<=n;j++)//从1号城市到n号城市依次尝试看是否能通过j到达n 
        {
            if(dist[cur][j]!=INF&&book[j]==0)//判断当前城市cur到城市j是否有路,并判断城市j是否已经走过
            {
                book[j]=1;//标记已经走过
                dfs(j,dis+dist[cur][j]);//从城市j再出发,继续寻找
                book[j]=0;
            }
        }
        return;
    }
    int main()
    {
        int i,j,m,a,b,c;
        cin>>n>>m;
        //初始化二维矩阵
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i==j)    dist[i][j]=0;   //到自己的距离为0
                    else    dist[i][j]=INF;  //距离为无限,默认到不了 
     
                //读入城市之间的距离
                for(i=1;i<=m;i++)
                {
                    cin>>a>>b>>c;
                    dist[a][b]=c;
                }
     
                //从1号城市出发,接下来就交给函数dfs了~ 
                book[1]=1;
                dfs(1,0);
                cout<<minn;
            return 0;
    }
    
    

     

    事实上,基于广度优先遍历依照节点到初始点的节点数遍历全图的特点,它能解决没有权值(也就是默认每条路程一样长)的图的最小路径问题,但对有权值的图,BFS很难解决(即使加上minn指标,我们也无法处理“回头”的路径)。我们就不在此讲解了。

    运行结果:

    Image

     

    2、Floyd算法

    Floyd它可以方便地求出任意两点间的距离,求的是多源最短路径。最大的优点就是容易理解和编写,算法的核心代码只有5行:

     //核心代码
         for(k=1;k<=n;k++)
             for(i=1;i<=n;i++)
                 for(j=1;j<=n;j++)
                    if(dist[i][k]+dist[k][j]<dist[i][j])
                         dist[i][j]=dist[i][k]+dist[k][j]; 

    我们可以把Floyd算法理解为“如果两点间的路径长度,大于这两点通通过第三点连接的路径长度,那么就修正这两点的最短路径”。

    下面我们来具体讲解一下算法的思路:

    在代码中,i,j表示的是我们当前循环中所求的起点、终点。k则是我们引入的“中转点”。为什么要引入中转点呢?因为当我们寻找i、j之间的最短路径时,要么是i、j间的距离,要么就是经过其他点中转:i→k→j

    为了方便讲解,我们给出一个概念“松弛”:如果dist【i】【j】>dist【i】【k】+dist【k】【j】(e表示两点间的距离),我们把dist【i】【j】更新为dist【i】【k】+dist【k】【j】,达到“经过中转点k后距离缩短,并记录”的目的。

    在第1轮循环中,我们以1为中转点,把任意两条边的距离松弛一遍,更新数组数据。

    在第2轮循环中,我们以2为中转点,再松弛一遍。这时,对第1轮松弛更新过的数据,如果继续更新,相当于中转到1,2后取得当前最短路径。

    。。。。。。

    最后得到的数组就是任意两点间的最短路径。

    下面放码。

    
    //Floyd算法解最短路径问题 
    #include <iostream>
    using namespace std;
    
    const int INF=99999;
    
    int main()
    {
      //读入数据的过程和dfs没什么区别,就不讲解了 
        int i,j,n,m,k,a,b,c;
        int dist[105][105];
        cin>>n>>m;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i==j)    dist[i][j]=0;  
                    else    dist[i][j]=INF;  
     
                for(i=1;i<=m;i++)
                {
                    cin>>a>>b>>c;
                    dist[a][b]=c;
                }
    
         //核心代码
         for(k=1;k<=n;k++)
             for(i=1;i<=n;i++)
                 for(j=1;j<=n;j++)
                    if(dist[i][k]+dist[k][j]<dist[i][j])
                         dist[i][j]=dist[i][k]+dist[k][j]; 
        
         for (i=1;i<=n;i++){
           for(j=1;j<=n;j++){
             cout<<dist[i][j]<<"\t";
         }
         cout<<endl;
       }
    
            return 0;
    }
    

    Image

     

    3、Dijkstra算法

    Dijkstra 算法主要解决的是单源最短路径问题。它的时间复杂度一般是o(n^2) ,因此相对于Floyd算法速度上有极大的优势,可以处理更多的数据。

    算法的核心依旧是上文讲到的“松弛”。只不过松弛的方式略有不同:它通过不断选择距离起点最近的顶点作为新的起点,再利用这些新的起点来松弛其他较远的点,最终计算出所有点到起点最短路径。

    我们把点i到起点1的距离定义为dis【i】(现在知道我上面为什么用dist了吧!),用一个book来标记该点是否已经为最短状况,初始化为0(否)

    核心代码分为两部分:第一部分判断最小,第二部分进行松弛。

    以原题为例:

    第一次循环,我们先进入第一部分判断较短距离。第一次到起点1只有2号,5号点有最短距离,分别为2,10。

    下一步,我们找到2,5号中到起点1距离较短的点u(这里是2号)。

    进入第二部分松弛。对点v,如果v到起点1的距离大于u(即2)到1的距离加上2到v的距离,更新v到原点的距离dis【v】。

    开始循环。

    下一次循环中,相当于把点2当作新的起点代替点1,进行上述操作。

    可以看出,Dijkstra是一种基于贪心策略的算法,也是一种以DFS为思路的算法。

    #贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,贪心算法所做出的是在某种意义上的局部最优解。#

    为什么下一条次较短路径要这样选择?(贪心准则的正确性)

    因为我们算的是到起点的距离,所以所有路径必然要经过与起点最近的2(或不经过任何别的中转点),而相对于2点,5号点距离更远,还有通过2点松弛之后缩短路径的可能性,所以我们直接选择2为新的起点进行下一步松弛。那么,第k次循环就表示松弛了k次,即经过 了k-1个中转点(或k-1条边)才到达起点1,留在dis()数组中的距离就是经过中转点个数<=k-1(可能无需经过这么多个点就达到)的最短路径。

    Dijkstra算法主要特点是以起始点为中心向外层层扩展,从一个顶点到其余各顶点的最短路径算法,直到扩展到最远点(指经过的中转点最多,)为止。(这里就是类似BFS的地方)

    选择最短路径顶点的时候依照的是实现定义好的贪心准则,所以该算法也是贪心算法的一种。

     

    下面给出代码。

    
    //Dijkstra算法解最短路径问题 
    #include<iostream>
    using namespace std;
    
    const int INF=99999;
    
    int main()
    {
         int dist[105][105] ;
       int dis[105]  ;
       int book[105] ;
       int i,j,n,m,a,b,c,u,v,Min;
    
         cin>>n>>m;
    
         //开始了!!!
         for(i = 1;i <= n;i++)  //每轮循环计算的是中转点为n-1时的最小点。
              for(j = 1;j <= n;j++)
                  if(i == j)  dist[i][j] = 0;
                  else        dist[i][j] = INF;
    
                  for(i = 1;i <= m;i++)
                  {
                        cin>>a>>b>>c;
                        dist[a][b] = c;
                  }
                  
              for(i = 1;i <= n;i++)        
                        dis[i] = dist[1][i];
    
              for(i = 1;i<=n;i++)   //初始化标记book 
                       book[i] = 0;
                       book[1] = 1;
    
              for(i = 1;i <= n-1;i++)  //筛出当前没有访问的并且与上一点直接相连的距离最小的点。
            {
                   Min = INF;
                   for(j = 1;j <= n;j++)
                   {
                         if(book[j] == 0&& dis[j] < Min)
                         {
                               Min = dis[j];
                               u = j;
                         }
                   }
    
    
              book[u] = 1;
              for(v = 1;v <= n;v++) //松弛
              {
                    if(dist[u][v] < INF)
                    {
                          if(dis[v] > dis[u] + dist[u][v])
                               dis[v] = dis[u] + dist[u][v];
                    }
              }
            }
            
            for(i  = 1;i <= n;i++)
                cout<<dis[i]<<"\t";
    
        return 0;
    }

             Image

     

    4、Bellman-Ford算法

    与Floyd算法一样,Dijkstra也有自己的问题,那就是无法处理“路径长度”的情况。(当然,城市间的距离不可能为负,但在一些特殊的问题中,路径的长度也可以为负)

    为什么呢?以第一次循环为例,我们在第一次判断选择了点2为“新起点”,而没有考虑别的点经过点5达到起点1松弛的可能性。假设,点3到点2的距离为1,点3到点5的距离为-100,那点3经过点5松弛的路径实际上更短,而在Dijkstra中,却被我们忽视了。

    所以,我们介绍Bellman-Ford算法来解决这种问题。

     //Bellman-Ford算法核心部分 
         for(k = 1;k <= n;k++)
             for(i = 1;i <= m;i++)
                if(dis[v[i]]>dis[u[i]]+w[i]) 
                   dis[v[i]] = dis[u[i]]  + w[i];
         for(i = 1;i <= m;i++)
                if(dis[v[i]]>dis[u[i]]+w[i])

    可以从代码中看到Bellman-ford与Dijkstra有相似的地方,都是通过松弛操作来达到最短路径。不同的是,Dijkstra是通过从近到远的顺序来按的顺序松弛,Bellman-ford则是按输入时对每一条的顺序来松弛。

    代码中的数组u(),v(),w()分别存储一行输入的三个数据(i点,j点,i到j的单向距离),这意味着在前文提到的邻接矩阵被我们弃用了,dist()数组不会在这里出现了。

    最外轮的k循环表示每次通过k个中转点(这里与Dijkstra相同,同样我们可以理解为经过的边的条数),i循环表示枚举m条边。

    看过前面对Dijkstra的讲解,这里应该不难理解了:对每一条编号为i的边,我们比较i的起点v[i]到起点1的距离dis[v[i]]i的另一点u[i]到起点1的距离+ v[i]u[i]的间距dis[u[i]]  + w[i],更新dis(j)。那么,第k次循环就表示松弛了k次,即经过 了k-1个中转点(或k-1条边)才到达起点1,留在dis()数组中的距离就是经过中转点个数<=k-1(可能无需经过这么多个点就达到)的最短路径。(细心的朋友可以发现这句话在前文中出现过)

    下面回到负值路径的问题上。因为我们是通过边为顺序松弛的,在这个过程中没有放弃对任何一条边(在Dijkstra中,我们放弃了部分数据,比如点5到点3的路径),所以不会有忽视的情况,自然也就能处理负值边了~

    我们甚至还能判断负权回路(指一个回路的路径总和为负)。

    等等,我们是不是还没提过为什么松弛n-1次后一定能得到最短路径?

    1. 当没有负权回路时,对于超过n-1条边而到达起点1的路径,一定存在正值回路,肯定可以去掉;

    2. 当有负权回路时,我们可以无限次地在回路里循环,让路径无限小,也就没有“最短路径了”。

    因此,n-1次的松弛必然得到最短路径。

    我们就基于2来判断负权回路。在循环n-1次后再对每一条边松弛一次,如果有还能继续松弛的边,则存在负权回路。

     

    我们来看看完整版代码:

    //Bellman-Ford算法解最短路径问题 
    #include<iostream>
    using namespace std;
    
    const int INF=99999;
    
    int main()
    {
         int dis[105] , i , k , n , m , u[105] , v[105] , w[105];
         bool flag=false;
         cin>>n>>m;
    
         for(i  = 1;i <= m;i++)
               cin>>u[i]>>v[i]>>w[i];
    
         for(i = 1;i <= n;i++)
              dis[i] = INF;
              
         dis[1] = 0;
    
         //Bellman-Ford算法核心部分 
         for(k = 1;k <= n;k++)
             for(i = 1;i <= m;i++)
                if(dis[v[i]]>dis[u[i]]+w[i]) 
                   dis[v[i]] = dis[u[i]]  + w[i];
         for(i = 1;i <= m;i++)
                if(dis[v[i]]>dis[u[i]]+w[i]) 
                     flag=true;
    
          if (!flag)
             for(i = 1;i <= n;i++)
                   cout<<dis[i]<<"\t";
          else
                cout<<"存在负权回路!!";
    
    }

                   Image

     

    5、SPFA算法

    之前我们在谈到Bellman-ford能处理负值路径是提到,Bellman-ford没有放弃对任何一条边的松弛。这虽然不错,但也会是我们优化的一个方向。

    我们可以加入一个判断,判断某一条边是否被别的点帮助松弛过,因为只有被松弛过的点才能松弛别的点(被起点松弛也是松弛)。当一个点无法被松弛时,在本次经过k-1条边,它还无法接触到起点1(或者在更早的时候就已经被判断过了),也就没有帮助他人的能力。这是一个递推的过程,需要想明白。如果存在有一个点压根就没能力支援,也就是它本身已经没有存在的价值了,那么我们下次就不用再考虑它了。

    注意,在这里我们依然我们始终保留了对负权路径、回路的判断。

    我们可以利用队列来存放可以继续帮助松弛的点,舍弃没有利用价值的点。这和BFS是一个道理,一边要保证有k-1轮大循环来控制,一方面又要舍弃旧点增加新点,队列就可以有这个作用。所以当代码写出来是你会惊讶地发现,它和BFS的形式是那么地相似。

    
    //SPFA解最短路径问题 
    #include <iostream>
    using namespace std;
    
    int main(){
      int n,m,i,j,k;
      int dis[105]={0},book[105]={0};
      //book数组用来记录哪些顶点已经在队列中 
      int que[1000]={0},head=1,tail=1;//定义一个队列,并初始化队列
      int dist[105][105];
      int INF = 99999999;
      int a,b,c;
      
      cin>>n>>m;
      //初始化 
      for(i=1;i<=n;i++)
        dis[i]=INF;
      dis[1]=0; 
      
      for(i=1;i<=n;i++)
        book[i] = 0; //初始化为0,刚开始都不在队列中
        
        //初始化二维矩阵
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i==j)    dist[i][j]=0;   //到自己的距离为0
                    else    dist[i][j]=INF;  //距离为无限,默认到不了 
     
                //读入城市之间的距离
                for(i=1;i<=m;i++)
                {
                    cin>>a>>b>>c;
                    dist[a][b]=c;
                }
     
      
          
      //1号顶点入队
      que[tail]=1; tail++;
      book[1]=1;//标记1号顶点已经入队
      
      while(head<tail){//队列不为空的时候循环
          for (i=1;i<=n;i++)
            if (dist[que[head]][i]!=INF && i!=que[head])
            {
              k=i;  // k表示每一条边的对应顶点 
              if(dis[k]>dist[que[head]][k]+dis[que[head]] ) //判断是否松弛成功
             { 
                    dis[k]=dist[que[head]][k]+dis[que[head]];
                  //这的book数组用来判断顶点v[k]是否在队列中
                    /*如果不使用一个数组来标记的话,判断一个顶点是否在队列中每次
                    都 需要从队列的head到tail扫一遍,很浪费时间*/
            
                  if(book[k]==0)//0表示不在队列中,将顶点v[k]加入队列中 
                   //下面两句为入队操作
                {
                  que[tail] = k;
                  tail++;
                  //同时标记顶点v[k]已经入队 
                book[k] =1;
                    }
            } 
          }
        //出队
        book[que[head]] = 0;
        head++; 
      }
      
      
      
      for(i=1;i<=n;i++)
        cout<<dis[i]<<"\t";
      
      return 0; 
    }

               Image

    注:

    #网上很多资料提到SPFA都会提到邻接表,这里我为了偷懒就随便讲下啦~~代码中我用的是邻接矩阵存储的,请放心食用。

    大致是因为,当图的边数较少时(相对于顶点而言,边数M<顶点数N^2)(我们称为稀疏图,对应稠密图),用这样的方法来存储可以极大地降低时间复杂度。

    大致是利用了链表的原理实现的。有兴趣可以自己搜索。#

     

    算法总结

     

     

     

    更多相关内容
  • lingo解最短路径问题

    2018-08-09 12:07:15
    lingo解最短路径问题。城市之间线路及距离已知。从某个城市出发,到达目的城市,通过lingo编程选取最短路径。
  • DQN最短路径MATLAB.zip,Basic Functions,q_value_or_policy2fig.m,make_greedy_policy.m,ds2nfu.m,sigmoid.m,make_random_policy.m,make_epsilon_policy.m,Environment,clcAngle.m,SAEnvironment.m,05 DQN,DQN.m,DQN...
  • 主要介绍了python Dijkstra算法实现最短路径问题的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • 脉冲耦合神经网络(PCNN)具有自动波特性,因此适合处理经典的最短路径问题。 但是,大多数方法表明,PCNN模型的自动波动在寻找最短路径时应保持恒定的速度。 针对最短路径问题,本文提出了一种新的自适应自动波脉冲...
  • 重点掌握:动态规划法求解每对结点之间的最短路径、0/1背包问题。 如果求任意两点之间的最短路径,两点之间可以直接到达但却不是最短的路径,要让任意两点(例如从顶点a点到顶点b)之间的路程变短,只能引入第三个点...
  • 遗传算法解决最短路径问题的matlab程序,并加以注释。 遗传算法解决最短路径问题的matlab程序,并加以注释。
  • 多段图的最短路径问题 动态规划法.cpp.rar,多段图的最短路径问题 动态规划法.cpp
  • 问题描述 若用有向网表示某地区的公路交通网其中顶点表示该地区的一些主要场所弧表示已有的公交线路弧上的权表示票价试设计一个交通咨询系统指导乘客以最少花费从该地区中的某一场所到达另一场所 基本要求 1 从文件...
  • 上机实验12 最短路径问题Dijkstra算法 最小生成树Kruskal算法和Prim算法 一最短路径问题Dijkstra算法 实验问题描述如图的交通网络每条弧上的数字代表车辆在该路段行驶所需的时间有向边表示单行道无向边表示可双向...
  • 在9个城市中,两两互通,通过遗传算法学习最短路径,基因库是所有路径,8个基因组成染色体。
  • 迪杰斯特拉(Dijkstra)算法主要是针对没有负值的有向图,求解其中的单一起点到其他顶点的最短路径算法。 1 算法原理 迪杰斯特拉(Dijkstra)算法是一个按照路径长度递增的次序产生的最短路径算法。下图为带权值的有...
  • 数据结构 c++ 图的最短路径问题 (邻接表) 数据结构 c++ 图的最短路径问题 (邻接表)
  • 本文研究了结合流水车间调度问题和最短路径问题获得的组合优化问题。 获得的问题的目的是选择构成最短路径问题的可行解决方案的作业的子集,并在流水车间的机器上执行所选的作业以最小化制造时间。 我们认为,即使...
  • 最短路径问题

    千次阅读 2021-01-12 20:37:24
    最短路径问题 系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 例如:第一章 Python 机器学习入门之pandas的使用 提示:写完文章后,目录可以自动生成,如何生成可参考右边的帮助...

    最短路径问题

    1.最短路径介绍

    最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。
    算法具体的形式包括:
    ①确定起点的最短路径问题即已知起始结点,求最短路径的问题。
    ②确定终点的最短路径问题与确定起点的问题相反,该问题是已知终点结点,求最短路径的问题。
    在无向图中该问题与确定起点的问题完全等同,
    在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
    ③确定起点终点的最短路径问题即已知起点和终点,求两结点之间的最短路径。
    ④全局最短路径问题求图中所有的最短路径。

    在这里插入图片描述

    用于解决最短路径问题的算法被称做“最短路径算法”, 有时被简称作“路径算法”。

    最常用的路径算法有:
    Bellman-Ford算法
    SPFA算法
    Dijkstra算法
    Floyd-Warshall算法

    2、常见算法

    ①Dijkstra算法

    是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。

    基本思想是:
    将顶点集合V分成两个集合,一-类是生长点的集合S,包括源点和已经确定最短路径的顶点;另一类是非生长点的集合V(s), 包括所有尚未确定最短路径的顶点,并使用一个待定路径表,存储当前从源点v到每个非生长点vi的最短路径。初始时,S只包含源点v,对v∈V(s),待定路径表为从源点v到vi的有向边。然后在待定路径表中找到当前最短路径v,…
    Vk, 将v加入集合S中,对vi∈V(s),将路径v, … vk, vi与待定路径表中从源点v到vi的最短路径相比较,取路径长度较小者为当前最短路径。重复上述过程,直到集合V中全部顶点加入到集合S中。
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述对图6-20(b)所示有向网执行Dijkstra 算法,求得从顶点vo到其余各顶点的最短路径,以及算法执行过程中数组dist 和path的变化状况,如表6-3所示。

    在这里插入图片描述
    代码:

    #include<stdio.h>
    #include<stdlib.h>
    #define max1 10000000  //原词条这里的值太大,导致溢出,后面比较大小时会出错
    int a[1000][1000];
    int d[1000];//d表示源节点到该节点的最小距离
    int p[1000];//p标记访问过的节点
    int i, j, k;
    int m;//m代表边数
    int n;//n代表点数
    int main()
    {
        scanf("%d%d",&n,&m);
        int    min1;
        int    x,y,z;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            a[x][y]=z;
            a[y][x]=z;
        }
        for( i=1; i<=n; i++)
            d[i]=max1;
        d[1]=0;
        for(i=1;i<=n;i++)
        {
            min1 = max1;
            //下面这个for循环的功能类似冒泡排序,目的是找到未访问节点中d[j]值最小的那个节点,
            //作为下一个访问节点,用k标记
            for(j=1;j<=n;j++)
                if(!p[j]&&d[j]<min1)
                {
                    min1=d[j];
                    k=j;
                }
            //p[k]=d[k]; // 这是原来的代码,用下一 条代码替代。初始时,执行到这里k=1,而d[1]=0
           //从而p[1]等于0,这样的话,上面的循环在之后的每次执行之后,k还是等于1。
            p[k] = 1; //置1表示第k个节点已经访问过了
            for(j=1;j<=n;j++)
                if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])
                    d[j]=d[k]+a[k][j];
        }
        //最终输出从源节点到其他每个节点的最小距离
        for(i=1;i<n;i++)
            printf("%d->",d[i]);
        printf("%d\n",d[n]); 
        return 0;
    }
    

    堆优化的迪杰斯特拉算法

    #include<bits/stdc++.h>
    #define M(x,y) make_pair(x,y)
    using namespace std;
    int fr[100010],to[200010],nex[200010],v[200010],tl,d[100010];
    bool b[100010];
    void add(int x,int y,int w){
        to[++tl]=y;
        v[tl]=w;
        nex[tl]=fr[x];
        fr[x]=tl;
    }
    priority_queue< pair<int,int> > q;
    int main(){
        int n,m,x,y,z,s;
        scanf("%d%d%d",&n,&m,&s);
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
        }
        for(int i=1;i<=n;i++) d[i]=1e10;
        d[s]=0;
        q.push(M(0,s));
        while(!q.empty()){
            int x=q.top().second;
            q.pop(); 
            if(b[x]) continue;
            b[x]=1;
            for(int i=fr[x];i;i=nex[i]){
                int y=to[i],l=v[i];
                if(d[y]>d[x]+l){
                    d[y]=d[x]+l;
                    q.push(M(-d[y],y));//懒得重载运算符
                }
            }
        }
        for(int i=1;i<=n;i++) printf("%d ",d[i]);
        return 0;
    }
    

    ②Bellman-Ford算法

    贝尔曼-福特算法(Bellman-Ford)是求解单源最短路径问题的一种算法。它的原理是对图进行V-1次松弛操作,得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达O(VE)。但算法可以进行若干种优化,提高了效率。

    Floyd算法用于求每一对顶点之间的最短路径问题,问题描述如下:给定带权有向图G=(V, E),对任意顶点vi和vj (i≠j) ,求顶点Vi到顶点Vj的最短路径。

    Floyd算法的基本思想是:
    假设从v;到v;的弧(若从v;到v;的弧不存在,则将其弧的
    权值看成∞)是最短路径,然后进行n次试探。首先比较vi, Vj和vi; vo, v;的路径长度,取长度较短者作为从vi到vj中间顶点的编号不大于0的最短路径。在路径上再增加一个顶点vI,将vi,…vI,…vj和已经得到的从vi到vj中间顶点的编号不大于0的最短路径相比较,取长度较短者作为中间顶点的编号不大于1的最短路径。
    依此类推,在一般情况下,若vi,…,vk和Vk,…vj分别是从vi到vk和从Vk到vj中间顶点的编号不大于k-1的最短路径,则将vi,…,vk,…,vj和已经得到的从vi到vj中间顶点的编号不大于k-1的最短路径相比较,取长度较短者为从vi到vj中间顶点的编号不大于k的最短路径。经过n次比较后,最后求得的必是从Vi到vj的最短路径。
    在这里插入图片描述
    伪代码表示

    procedure BellmanFord(list vertices, list edges, vertex source)
       // 该实现读入边和节点的列表,并向两个数组(distance和predecessor)中写入最短路径信息
     
       // 步骤1:初始化图
       for each vertex v in vertices:
           if v is source then distance[v] := 0
           else distance[v] := infinity
           predecessor[v] := null
     
       // 步骤2:重复对每一条边进行松弛操作
       for i from 1 to size(vertices)-1:
           for each edge (u, v) with weight w in edges:
               if distance[u] + w < distance[v]:
                   distance[v] := distance[u] + w
                   predecessor[v] := u
     
       // 步骤3:检查负权环
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               error "图包含了负权环"
    

    ③*SPFA算法

    SPFA(最短路径快速算法,英语:Shortest Path Faster Algorithm)是一个用于求解有向带权图单源最短路径的改良的贝尔曼-福特算法。这一算法被认为在随机的稀疏图上表现出色,并且极其适合带有负边权的图。然而SPFA在最坏情况的时间复杂度与贝尔曼-福特算法相同,因此在非负边权的图中仍然最好使用迪杰斯特拉算法(Dijkstra)。

    SPFA算法的基本思路与贝尔曼-福特算法相同,即每个节点都被用作用于松弛其相邻节点的备选节点。相较于贝尔曼-福特算法,SPFA算法的提升在于它并不盲目尝试所有节点,而是维护一个备选节点队列,并且仅有节点被松弛后才会放入队列中。整个流程不断重复直至没有节点可以被松弛。

    下面我们采用SPFA算法对下图求v1到各个顶点的最短路径:
    在这里插入图片描述
    初始化:

    首先我们先初始化数组dis如下图所示:(除了起点赋值为0外,其他顶点的对应的dis的值都赋予无穷大,这样有利于后续的松弛)
    在这里插入图片描述
    此时,我们还要把v1如队列:{v1}
    现在进入循环,直到队列为空才退出循环。

    第一次循环:

    首先,队首元素出队列,即是v1出队列,然后,对以v1为弧尾的边对应的弧头顶点进行松弛操作,可以发现v1到v3,v5,v6三个顶点的最短路径变短了,更新dis数组的值,得到如下结果:
    在这里插入图片描述我们发现v3,v5,v6都被松弛了,而且不在队列中,所以要他们都加入到队列中:{v3,v5,v6}

    第二次循环

    此时,队首元素为v3,v3出队列,然后,对以v3为弧尾的边对应的弧头顶点进行松弛操作,可以发现v1到v4的边,经过v3松弛变短了,所以更新dis数组,得到如下结果:

    在这里插入图片描述此时只有v4对应的值被更新了,而且v4不在队列中,则把它加入到队列中:{v5,v6,v4}

    第三次循环

    此时,队首元素为v5,v5出队列,然后,对以v5为弧尾的边对应的弧头顶点进行松弛操作,发现v1到v4和v6的最短路径,经过v5的松弛都变短了,更新dis的数组,得到如下结果:

    在这里插入图片描述我们发现v4、v6对应的值都被更新了,但是他们都在队列中了,所以不用对队列做任何操作。队列值为:{v6,v4}

    第四次循环

    此时,队首元素为v6,v6出队列,然后,对以v6为弧尾的边对应的弧头顶点进行松弛操作,发现v6出度为0,所以我们不用对dis数组做任何操作,其结果和上图一样,队列同样不用做任何操作,它的值为:{v4}

    第五次循环

    此时,队首元素为v4,v4出队列,然后,对以v4为弧尾的边对应的弧头顶点进行松弛操作,可以发现v1到v6的最短路径,经过v4松弛变短了,所以更新dis数组,得到如下结果:

    在这里插入图片描述因为我修改了v6对应的值,而且v6也不在队列中,所以我们把v6加入队列,{v6}

    第六次循环

    此时,队首元素为v6,v6出队列,然后,对以v6为弧尾的边对应的弧头顶点进行松弛操作,发现v6出度为0,所以我们不用对dis数组做任何操作,其结果和上图一样,队列同样不用做任何操作。所以此时队列为空。

    OK,队列循环结果,此时我们也得到了v1到各个顶点的最短路径的值了,它就是dis数组各个顶点对应的值,如下图:

    在这里插入图片描述

    int SPFA(int s) {
          queue<int> q;
          bool inq[maxn] = {false};
          for(int i = 1; i <= N; i++) dis[i] = 2147483647;
          dis[s] = 0;
          q.push(s); inq[s] = true;
          while(!q.empty()) {
              int x = q.front(); q.pop();
              inq[x] = false;
             for(int i = front[x]; i !=0 ; i = e[i].next) {
                 int k = e[i].v;
                 if(dis[k] > dis[x] + e[i].w) {
                     dis[k] = dis[x] + e[i].w;
                     if(!inq[k]) {
                         inq[k] = true;
                         q.push(k);
                     }
                 }
             }
         }
         for(int i =  1; i <= N; i++) cout << dis[i] << ' ';
         cout << endl;
         return 0;
     }
    

    松弛

    每次松弛操作实际上是对相邻节点的访问,第n次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过|V|-1条边,所以可知贝尔曼-福特算法所得为最短路径。

    负边权操作

    与迪杰斯特拉算法不同的是,迪杰斯特拉算法的基本操作“拓展”是在深度上寻路,而“松弛”操作则是在广度上寻路,这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。
    正权图使用dijkstra算法,负权图使用SPFA算法

    负权环判定

    因为负权环可以无限制的降低总花费,所以如果发现第
    次操作仍可降低花销,就一定存在负权环。

    ④Floyd - Warshall(弗洛伊德算法)

    模板模板
    视频资源:
    https://www.bilibili.com/video/BV1LE411R7CS?from=search&seid=1868101711902580696

    参考博客:
    https://blog.csdn.net/qq_35644234/article/details/61614581

    https://blog.csdn.net/sugarbliss/article/details/86511043?ops_request_misc=%25257B%252522request%25255Fid%252522%25253A%252522161043542716780255270397%252522%25252C%252522scm%252522%25253A%25252220140713.130102334…%252522%25257D&request_id=161043542716780255270397&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2alltop_click~default-1-86511043.first_rank_v2_pc_rank_v29&utm_term=%E6%9C%80%E7%9F%AD%E8%B7%AF

    展开全文
  • 最短路径问题 大一数据结构最短路径问题
  • 最短路径问题(python实现) 解决最短路径问题:(如下三种算法) (1)迪杰斯特拉算法(Dijkstra算法) (2)弗洛伊德算法(Floyd算法) (3)SPFA算法 第一种算法: Dijkstra算法 广度优先搜索解决赋权有向图或者...
  • 通过学习ACO算法来解释城市最短路径问题的算法。
  • 基于最短路径问题提出了带有启 发信息的遗传算法思想,将启发信息加入到了初始种群生成过程中,提出了新的交叉方法。通 过模拟仿真得到了算法的性能参数,并将本文算法和Dijkstra算法进行比较,结果表明,在求 解数据规模...
  • 在本文中,我们有兴趣通过排名方法解决组合优化问题,即多属性图中的最短路径问题。 多属性图同时具有定性和定量标准。 这种情况导致无法比拟的路径,从而形成帕累托阵线。 多准则决策(MCDM)中的排名方法是唯一...
  • 采用的是分枝定界算法,效率较低
  • 阐述了带转向延误和限制的最短路径问题(SP Turn)的基本原理,系统介绍了现有的求解方法,包括扩展网络法、对偶网络法和弧标号算法,并提出了一个节点标号算法用于对比。分析指出弧标号、节点标号算法在算法原理上...
  • 设计一个旅游景点导游模拟程序,为来访的客人提供景点最短路径的信息查询服务,任意选取n城市,构成一个有向带权图,图中顶点表示城市,边上的权值表示两点间的距离,根据用户指定的始点和终点输出相应的最短路径
  • 一次函数之最短路径问题PPT课件.pptx

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 218,452
精华内容 87,380
关键字:

最短路径问题