03 最短路 dijkstra算法&spfa算法&floyd算法（附带实例代码） 图论-1

文章目录

• • 最短路
  • • 邻接表的图如下
    • 邻接矩阵如下图
    • 链表实现邻接表实现代码
  • 单源最短路径
  • • Dijkstra 算法
    • • 朴素版本 Dijkstra 实现代码
      • 堆优化的dijkstra算法代码实现
    • Bellman-Ford 算法和 SPFA 算法
    • • SPFA算法的代码实现
    • 任意两点间的最短距离
    • Floyd 算法
    • • Floyd 算法代码实现

最短路

1. 对于一条有向图，我们一般采用邻接矩阵和邻接表两种存储方式。
   

   
   

   对于无向图，可以把看无向边看作两条方向相反的有向边。
   

   
   

   从而采用与有向图一样的存储方式。
   

   
   

邻接表的图如下

邻接矩阵如下图

链表实现邻接表实现代码

/// 加入有向边（a,b）,权值为c
void (int a,int b)
{ 
	e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++; 
}

/// 访问从a出发的所有边
for(int i=h[a]; ~i; i = ne[i])
{
	int b = e[i],c = w[i]; 
}

单源最短路径

1. 单源最短路径问题是说，给定一张有向图 G = （V,E）,V是点集，E是边集, |V| = n,|E| = m,节点以 [1,n] 之间的连续整数编号，（x，y，z） 描述一条从 x 出发，到达y，长度为z的有向边。
   

   
   

   设 1 号点为起点，求长度为 n 的数组 dist，其中 dist[i] 表示从起点 1 到节点 i 的最短路径的长度。
   

   
   

Dijkstra 算法

Dijkstra 算法的流程如下。

1. 初始化 dist[1] = 0, 其余节点的 dist 值为正无穷大。
   

   
   

2. 找出一个未被标记的，dist[x] 最小的节点x，然后标记节点 x。
   

   
   

3. 扫描节点 x 的所有出边（x,y,z）,若 dist[ y ] > dist[ x ] + z,则使用 dist[ x ] + z 更新 dist [ y ]
4. 重复上述 2 ~ 3 两个步骤，直到所有节点都被标记。
   

   
   

   
   Dijkstra 算法基于贪心的思想，它只适用于所有边的长度都是非负数的图。
   

   
   

   当边长 z 都是非负数时，全局最小值不可能在被其他节点更新，故在第一步中选出的节点 x 必然满足：dist[ x ]已经是起点到 x 的最短路径。
   

   
   

   我们不断选择全局最小值的进行标记和扩展，最终可以得到起点 1 到每个节点的最短路径的长度。
   

   
   

朴素版本 Dijkstra 实现代码

#include 
#include 
#include 
#include 

using namespace std;

const int N = 3010;
int a[N][N],d[N],n,m;
bool v[N];

void dijkstra()
{
    memset(d,0x3f,sizeof d);  // dist 数组
    memset(v,0,sizeof v);     // 节点标记
    d[1] = 0;
    for(int i=1; i<n; i++)   // 重复进行 n-1 次 
    {
        int x = 0;
        // 找到未标记节点中 dist 最小的
        for(int j=1; j<=n; j++)
            if(!v[j]&&(x==0||d[j]<d[x])) x = j;
        v[x] = 1;
        
        // 用全局最小值点x更新其他节点
        for(int y=1; y<=n; y++)
            d[y] = min(d[y],d[x]+a[x][y]);
    }
    
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    memset(a,0x3f,sizeof a);
    for(int i=1; i<=n; i++) a[i][i] = 0;
    for(int i=1; i<=m; i++)
    {
        int x,y,z; cin>>x>>y>>z; 
        a[x][y] =  min(a[x][y],z);   /// 采用邻接矩阵存图 
    }
    dijkstra();
    for(int i=1; i<=n; i++) 
        cout<<d[i]<<"\n";
    
    return 0;
}

朴素版本的dijkstra 的时间复杂度为 O（n²）,主要瓶颈在于第1 步的寻找全局最小值的过程。

可以用二叉堆（c++STL prority_queue）对dist 数组进行维护，用 O（log n）的时间获取最小值并从堆中删除，用 O（log n） 的时间执行一条边的扩展和更新，最终可在 O（m log n） 的时间内实现Dijkstra 算法。

堆优化的dijkstra算法代码实现

#include 
#include 
#include 
#include 
#include 

using namespace std;
const int N = 1e5+10,M = 1e6+10;
int h[N],e[M],w[M],ne[M],d[N];
bool st[N];
int n,m,idx;


// 大根堆 （优先队列），pair的第二维为节点编号
// pair 的第一维为dist的相反数（利用相反数变成小根堆）

priority_queue< pair <int,int> > q;
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}

void dijkstra()
{
    memset(d,0x3f,sizeof d);    // dist数组
    memset(st,0,sizeof st);     // 节点标记
    d[1] = 0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        // 取出堆顶
        int x = q.top().second; q.pop();
        if(st[x]) continue;
        
        // 扫描出所有出边
        for(int i=h[x]; ~i; i = ne[i])
        {
            int y = e[i],z =w[i];
            if(d[y]>d[x]+z)
            {
                d[y] = d[x]+z;
                q.push(make_pair(-d[y],y));
            }
        }
        
                
        
    }
    
    
}



int main()
{
    
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    
    memset(h,-1,sizeof h); /// 初始化链表的头结点
    /// 构建邻接表存储边
    for(int i=1; i<=m; i++)
    {
        int a,b,c; cin>>a>>b>>c;
        add(a,b,c);
    }
    
    /// 求单源最短路径
    dijkstra();
    for(int i=1; i<=n; i++)
        cout<<d[i]<<"\n";
    
    return 0;
}

Bellman-Ford 算法和 SPFA 算法

给定一张有向图，若对于图中的某一条边（x,y,z）,有 dist [y] <= dist[x] + z成立，则称该边满足三角形不等式。

若所有边都满足三角形不等式，则 dist 数组就是所求最短路。

我们介绍基于迭代思想的Bellman-Ford算法。

流程如下。

1. 扫描所有的边 （x,y,z）,若 dist[y] > dist[x] + z,则用 dist[x] + z 更新 dist [y]。
   

   
   

2. 重复上述步骤，直到没有更新 *** 作发生。
   

   
   

   
   Bellman-ford 算法的时间复杂度为 O（nm）

实际上，SPFA算法在国际上统称为“队列优化的Bellman-Ford算法”，仅在中国大陆流行“SPFA算法”的称谓。

SPFA 算法流程如下。

1， 建立一个队列，最初队列中只含有起点1
2， 取出队头节点 x，扫描它的所有出边（x，y，z），若dist[y] > dist[x] + z,则使用 dist[x] +z 更新 dist [ y ]。

同时，若y不在队列中，则把y入队。

3，重复上述步骤，直到队列都为空。

在任意时刻，该算法的队列都保存了待扩展的节点。

每次入队相当于完成一次dist数组的更新 *** 作，使其满足三角形不等式。

一个节点可能会入队，出队多次。

最终图中节点收敛到全部满足三角形不等式的状态。

这个队列避免了Bellman-Ford 算法中对不需要扩展的节点的冗余扫描，在随机图上运行效率为O（km）级别，其中k是一个较小的常数。

但在特殊构造的图上，该算法很可能退化为 O（nm），必须谨慎使用。

SPFA算法的代码实现

#include 
#include 
#include 
#include 
#include 

using namespace std;
const int N = 1e5+10,M = 1e6+10;
int h[N],e[M],w[M],ne[M],d[N];
bool st[N];
int n,m,idx;

queue<int> q;

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

void spfa()
{
    memset(d,0x3f,sizeof d);    // dist数组
    memset(st,0,sizeof st);     // 节点标记
    d[1] = 0; st[1] = true;
    q.push(1);
   
    while(!q.empty())
    {
        // 取出队头
        int x = q.front(); q.pop();
        st[x]=0;
        
        // 扫描出所有出边
        for(int i=h[x]; ~i; i = ne[i])
        {
            int y = e[i],z =w[i];
            if(d[y]>d[x]+z)
            {
                d[y] = d[x]+z;
                if(!st[y]) q.push(y),st[y] =1;
            }
        }
        
                
        
    }
    
    
}



int main()
{
    
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    
    memset(h,-1,sizeof h); /// 初始化链表的头结点
    /// 构建邻接表存储边
    for(int i=1; i<=m; i++)
    {
        int a,b,c; cin>>a>>b>>c;
        add(a,b,c);
    }
    
    /// 求单源最短路径
    spfa();
    for(int i=1; i<=n; i++)
        cout<<d[i]<<"\n";
    
    return 0;
}

图中存在长度为负数的边，Bellman-Ford 和SPFA算法也能够正常工作。

另外，如果图中不存在长度为负数的边，那么类似于优先队列的BFS，我们也可以使用二叉堆（c++ STL priority_queue） 对SPFA 算法进行优化，堆代替了一般的队列，用于保存待扩展的节点，每次取出“当前距离最小” 的节点（堆顶）进行扩展，节点第一次从堆中被取出时，就得到了该点的最短路。

这与堆优化 Dijkstra 算法的流程完全一致。

“二叉堆优化基于贪心的 Dijkstra 算法” 和 “优先队列优化基于 BFS 的SPFA算法” 两种思想殊途同归，都得到了非负权图上 O（mlogn） 的单元路径算法。

任意两点间的最短距离

为了求出图中任意两点间的最短路，当然可以把每个点作为起点，求解 N 次单源最短路径问题。

不过，在任意两点间的最短路问题中，图一般比较稠密。

使用 Floyd 算法可以在 O（N³）的时间内完成求解，并且程序实现非常简单。

Floyd 算法

设 D[k,i,j] 表示“经过若干个编号不超过 k 的节点” 从 i 到 j 的最短路长度。

该问题可划分为两个子问题，经过编号不超过 k-1 的节点从 i 到 j，或者从 i 先到 k 再到 j。

于是：
D[k,i,j] = min(D[k-1,i,j],D[k-1,i,k] + D[k-1,k,j] )

初值为 D[0,i,j] = A[i,j],其中 A 为本节开头定义的邻接矩阵。

可以看到，Floyd 算法的本质是动态规划。

k 是阶段，所以必须置于最外层循环中。

i 和 j 是附加状态，所以应该置于内置循环。

这也解释了为何很多初学者按照 i，j，k的顺序执行循环，会得到错误的结果。

与背包问题的状态转移方程类似，k这一维可被省略。

最初，我们可以直接用 D保存邻接矩阵，然后执行动态规划的过程。

当最外层循环到 k 时，内层有状态转移：
D[i,j] 就保存了 i 到 j的最短路长度。

Floyd 算法代码实现

#include 
#include 
#include 
#include 

using namespace std;
const int N =  310;
int d[N][N],n,m;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    memset(d,0x3f,sizeof d);
    for(int i=1; i<=n; i++) d[i][i] = 0;
    for(int i=1; i<=m; i++)
    {
        int x,y,z; cin>>x>>y>>z;
        d[x][y] = min(d[x][y],z);
    }
    
    /// 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]);
                
    
    
    /// 输出
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++) cout<<d[i][j]<<" "; 
        cout<<"\n";
    }
    return 0;
}