图的算法专题——最短路径-白红宇

图的算法专题——最短路径

阅读量：4313 次

发布时间：2019-06-06

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

概要：

Dijkstra算法

Bellman-Ford算法

SPFA算法

Floyd算法

1、Dijkstra算法用于解决单源最短路径问题，严格讲是无负权图的最短路径问题。

邻接矩阵版

1 const int maxv=1000; 2 const int INF=1000000000; 3 int n,G[maxv][maxv]; 4 int d[maxv];  //起点到各点的最短路径长度 5 bool vis[maxv]={
    false}; 6  7 void Dijkstra(int s){ //s为起点 8     fill(d,d+maxv,INF); 9     d[s]=0;10     for(int i=0;i

邻接表版

1 struct Node{ 2     int v,dis; //v为边的目标顶点， dis为边权 3 }; 4 vector
     
       Adj[maxv]; 5 int n,d[maxv]; 6 bool vis[maxv]={
    0}; 7  8 void Dijkstra(int s){ 9     fill(d,d+maxv,INF);10     d[s]=0;11     for(int i=0;i

若要求输出最短路径，以邻接矩阵为例：

1 const int maxv=1000; 2 const int INF=1000000000; 3 int n,G[maxv][maxv]; 4 int d[maxv];  //起点到各点的最短路径长度 5 bool vis[maxv]={
    false}; 6 int pre[maxv]; 7  8 void Dijkstra(int s){ //s为起点 9     fill(d,d+maxv,INF);10     for(int i=0;i

另外还有一种情况，如果某个结点存在多个前驱结点，那上面这种pre数组的方法就不再适用，改成vector即可：

1 const int maxv=1010; 2 const int INF=1000000000; 3 vector
     
       pre[maxv]; 4 void Dijkstra(int s){ 5     fill(d,d+maxv,INF); 6     d[s]=0; 7     for(int i=0;i

当访问的结点是路径起点st时（边界），此时tempPath里存了整条路径（倒序），这时需要计算第二标尺value的值，并与optValue比较，若更优则更新optValue并把path覆盖。

1 const int maxv=1010; 2 const int INF=1000000000; 3 int optValue; 4 vector
     
       path,tempPath; 5 vector
      
        pre[maxv]; 6  7 void Dijkstra(int s){ 8     fill(d,d+maxv,INF); 9     d[s]=0;10     for(int i=0;i

除此之外，还会碰到第二标尺，常见有以下三种：（具体代码见晴神算法笔记，写的很清楚）

新增边权（如增加开销）

新增点权（如收集到的物资）

求最短路径条数

2、Bellman-Ford 算法

算法流程：

（1）初始化：将除起点s外所有顶点的距离数组置无穷大 d[v] = INF, d[s] = 0

（2）迭代：遍历图中的每条边，对边的两个顶点分别进行一次松弛操作，直到没有点能被再次松弛

（3）判断负圈：如果迭代超过V-1次，则存在负圈

算法优点：

（1）可以检测负环，最坏情况下是进行n-1轮操作，若超过n-1轮后还有松弛说明有负环

算法缺点：

（1）在无负环的情况下，效率比Dijkstra低

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
            8 #include 
            
              9 using namespace std;10 const int MAXV=1000;11 const int INF=1000000000;12 struct Node{13 int v,dis; //v为邻接边的目标顶点，dis为邻接边的边权 14 };15 vector
             
               Adj[MAXV]; //图G的邻接表 16 int n;//顶点数17 int d[MAXV];//起点到达各点的最短路径长度18 bool flag;//用于优化 19 20 bool Bellman(int s){21 fill(d,d+MAXV,INF);22 d[s]=0;23 24 for(int i=0;i

3、SPFA算法

SPFA算法是在Bellman-ford算法的基础上进行改进，依据是每次松弛只会影响被松弛结点的相邻结点，于是将那些顶点加入队列，一直松弛到队列为空。

1 //bellman算法的改进SPFA 2 //由于bellman算法的每轮操作都需要操作所有的边，但只有当u的d[u]改变时，才会改变他的邻接点v的d[v]。  3 //设立一个队列保存待优化的节点， 4 //优化时每次取出队首节点u，并用u点当前的最短路径估计值对离开u点所指向的节点v进行松弛操作， 5 //且v点不在当前的队列中，就将v放入队尾，直到队列空  6  7 #include 
     
       8 #include 
      
        9 #include 
       
        10 #include 
        
         11 #include 
         
          12 #include 
          
           13 #include 
           14 #include 
            
             15 using namespace std;16 struct Node{17 int v,dis; //v为邻接边的目标顶点，dis为邻接边的边权 18 };19 const int MAXV=510;20 const int INF=1000000000;21 vector
             
               Adj[MAXV];22 int n,d[MAXV],num[MAXV];23 bool inq[MAXV];24 25 bool SPFA(int s){26 memset(inq,false,sizeof(inq));27 memset(num,0,sizeof(num));28 fill(d,d+MAXV,INF);29 30 queue
              
                Q;31 Q.push(s);32 inq[s]=true;33 num[s]++; //源点入队次数加134 d[s]=0;35 //主体部分36 while(!Q.empty()){37 int u=Q.front();//队首顶点编号为u 38 Q.pop(); 39 inq[u]=false;//设置u不在队列中40 //遍历u的所有邻接边v41 for(int j=0;j
               
                =n) return false; //若v入队次数大于n-1说明有负环 51 }52 }53 } 54 55 } 56 }

4、Floyd算法

算法流程：

枚举结点k（1到n），以k为中介点，枚举所有顶点对 i 和 j 进行松弛。

即 if (dis[i][k]+dis[k][j]<dis[i][j] ) dis[i][j]=dis[i][k]+dis[k][j];

1 //floyd算法：解决全源最短路问题 n^3复杂度，n限制约为200以内  2  #include
     
       3  #include
      
        4  using namespace std; 5  const int INF=1000000000; 6  const int MAXV=200; 7  int n,m;//n为顶点数，m为边数 8  int dis[MAXV][MAXV]; 9  10 void Floyd(){11      for(int k=0;k

转载于:https://www.cnblogs.com/Mered1th/p/10418946.html

你可能感兴趣的文章