LinJHS个人小站

原创 首页 算法

最短路问题：从 Dijkstra 到 Johnson

LinJHS 0

前言

最短路问题 (short-path problem) 是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

基本内容是：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。

单源最短路径

包括确定起点的最短路径问题，确定终点的最短路径问题（与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。） 。

求解单源最短路径问题可以采用 Dijkstra 算法，时间复杂度为 O(|V|^2) 。Dijkstra 算法可以使用斐波那契堆、配对堆等支持 Decrease-Key 操作的数据结构来进一步优化，优化后的时间复杂度为 O(|E|+|V|log|V|) 。

Dijkstra 只可求无负权的最短路径，因为其目光短浅，看不到后面可以消减的量。在正数中容易得证，若图中存在负权路径，则答案不一定正确。

如果图中有负权回路，可以采用 Bellman-Ford 算法，算法复杂度是 O(|V||E|) 。但 Bellman-ford 算法浪费了许多时间做无必要的松弛，可用 SPFA 算法进行优化，SPFA 算法是用队列进行的优化，优化后时间复杂度为 O(k|E|) ， 其中 k 为所有顶点进队的平均次数，可以证明 k 一般小于等于 2 ，由此可见该优化的效果十分显著。

一、Dijkstra 算法

首先，引入一个辅助数组 D ，它的每个元素 D[i] 表示当前所找到的从起始点（即源点 v ）到其它每个顶点 v_i 的长度。

例如，D[3]=2 表示从起始点到顶点 3 的路径相对最小长度为 2 。这里强调相对就是说在算法执行过程中，D 的值是在不断逼近最终结果，但在过程中不一定就等于长度。

  • D 的初始状态为：若从 v 到 v_i 有弧（即从 v 到 v_i 存在连接边），则 D[i] 为弧上的权值（即为从 v 到 v_i 的边的权值）；否则置 D[i] 为 \infty。

  • 接着，找到距离 v 最近的点 v_j ，并将 v_j 打上标记。

  • 用 v_j 更新与 v_j 相邻的且未被标记点 v_i 的 D[i] ，D[i]=min(D[i],D[j]+dis[j][i]) 。然后找到距离 v 最近的未被标记的点 v_j' ，更新成 v_j 。

  • 重复以上步骤，直到所有点均被标记。

Dijkstra 算法 + 堆优化

堆优化：

  1. 使用优先队列来代替最近距离的查找；

  2. 用邻接表代替邻接矩阵。

关于优先队列的操作：

struct node{
    int id;
    int dis;
};

bool operator < (node a,node b)
{
    return a.dis<b.dis;
}

priority_queue<node> a;

初始化：将起始点加入优先队列中，dis 为 0 。

每次操作结点时，都需要将更新后的结点加入优先队列中。

在当前点更新完四周的点时，弹出优先队列中最小的点。若最小点已经被标记过，则忽略它，再弹出一个点，直到找到未标记点。

核心代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, w;
};
vector<Edge> adj[MAXN];
int dis[MAXN];
bool vis[MAXN];

void dijkstra(int s)
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    dis[s] = 0;
    q.push(make_pair(0, s));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = 0; i < (int)adj[u].size(); i++) {
            int v = adj[u][i].to, w = adj[u][i].w;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                q.push(make_pair(dis[v], v));
            }
        }
    }
}

二、Bellman-Ford 算法

总体思路：

循环枚举每一条边，枚举 V-1 次（其中，V 为点数），并用枚举到的每一条边更新每个节点的最小值（即松弛操作）。

注意点：

  • 循环的提前跳出：当某次循环不再进行松弛时，直接退出循环，进行负权环判定。

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

  • 可以进行队列优化，详见 SPFA 算法。

三、SPFA 算法

SPFA 算法是 Bellman-Ford 算法的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 O(VE)。

具体做法：

  • 设立一个先进先出的队列用来保存待优化的结点。

  • 优化时每次取出队首结点 u ，并且用 u 点对其所指向的结点 v 进行松弛操作。

  • 如果 v 点的最短路径估计值有所调整，且 v 点不在当前的队列中，就将 v 点放入队尾。

  • 这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

证明如下：

每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点 v 的最短路径估计值 d[v] 变小。所以算法的执行会使 d 越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着 d 值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。

负环的判定：

实际上，如果一个点进入队列达到 n 次（这里的 n 为总点数，则表明图中存在负环，没有最短路径。

优化：

SPFA算法有两个优化策略 SLF 和 LLL 。

  • SLF：Small Label First 策略，设要加入的节点是 j ，队首元素为 i ，若 dist[j]<dist[i] ，则将 j 插入队首，否则插入队尾；

  • LLL：Large Label Last 策略，设队首元素为 i ，队列中所有 dist 值的平均值为 x ，若 dist[i]>x ，则将 i 插入到队尾，查找下一元素，直到找到某一 i 使得 dist[i]<=x ，则将 i 出队进行松弛操作。

SLF 和 LLF 在随机数据上表现优秀，但是在正权图上最坏情况为 O(VE) ，在负权图上最坏情况为达到指数级复杂度。

参考代码（改编自百度百科）：

#include <iostream>
#include <vector>
#include <list>
using namespace std;

struct Edge {
    int to,len;
};

bool spfa(const int &beg,//出发点
          const vector<list<Edge> > &adjlist,//邻接表，通过传地址避免拷贝
          vector<int> &dist,//出发点到各点的最短路径长度
          vector<int> &path)//路径上到达该点的前一个点
{//没有负权回路返回 0 ，有负权回路返回 1
    const int INF=0x7FFFFFFF;
    int NODE=adjlist.size();//用邻接表的大小传递顶点个数，减少参数传递
    dist.assign(NODE,INF);//初始化距离为无穷大
    path.assign(NODE,-1);//初始化路径为未知
    list<int> que(1,beg);//处理队列，现将起始点加入队列
    vector<int> cnt(NODE,0);//记录各点入队次数，用于判断负权回路
    vector<bool> flag(NODE,0);//标志数组，判断是否在队列中

    dist[beg]=0;//出发点到自身路径长度为0
    cnt[beg]=flag[beg]=1;//初始化起点的入队次数并标记其在队列中
    while(!que.empty())
    {
        const int now=que.front();
        que.pop_front();
        flag[now]=0;//将当前处理的点出队

        for(list<Edge>::const_iterator//用常量迭代器遍历邻接表
                i=adjlist[now].begin(); i!=adjlist[now].end(); i++)
            if(dist[i->to]>dist[now]+i->len)//可以进行松弛操作
            {
                dist[i->to]=dist[now]+i->len;//更新指向的结点的距离
                path[i->to]=now;//记录指向的结点的前一位，即倒序答案路径
                if(!flag[i->to])//若指向的结点未在处理队列中
                {
                    if(NODE==++cnt[i->to])//如果当前节点进入队列次数达到顶点个数
                        return 1;//出现负权回路
                    if(!que.empty() && dist[i->to]<dist[que.front()])//队列非空且优于队首（SLF）
                        que.push_front(i->to);//放在队首
                    else
                        que.push_back(i->to);//否则放在队尾
                    flag[i->to]=1;//将指向的节点标记
                }
            }
    }
    return 0;
}

int main()
{
    int n_num;//点数
    int e_num;//边数
    int beg;//出发点
    cout<<"输入点数、边数、出发点：";
    cin>>n_num>>e_num>>beg;
    vector<list<Edge> > adjlist(n_num,list<Edge>());//默认初始化邻接表
    for(int i=0,p; i!=e_num; i++)
    {
        Edge tmp;
        cout<<"输入第"<<i+1<<"条边的起点、终点、长度：";
        cin>>p>>tmp.to>>tmp.len;
        adjlist[p].push_back(tmp);
    }
    vector<int> dist,path;//用于接收最短路径长度及路径各点
    if(spfa(beg,adjlist,dist,path))
        cout<<"图中存在负权回路\n";
    else
        for(int i=0; i!=n_num; i++)
        {
            cout<<beg<<"到"<<i<<"的最短距离为"<<dist[i]<<"，反向打印路径：";
            for(int w=i; path[w]>=0; w=path[w])cout<<w<<"<-";
            cout<<beg<<'\n';
        }
}

全源最短路径

求图中所有的最短路径可以采用 Floyd-Warshall 算法，算法时间复杂度为 O(|V|^3) 。

对于稀疏图，还可采用 Johnson 算法，其采用 Bellman-ford 和 Dijkstra 作为其子函数，时间复杂度为 O(VElgV) 。

二者都可计算含负权路径的图，但不可含有负环。

两点最短路径

即已知起点和终点，求两结点之间的最短路径。在无权图中通常可以用广度优先搜索（BFS）、深度优先搜索（DFS）等方式来实现，时间复杂度是 O(|V|) 。

注：部分资料来源于百度百科

分享
如果这篇文章帮到你，可以请我喝一杯茶。

微信扫码打开

请我喝杯茶

如果这篇文章帮到你，可以请我喝一杯茶。

微信收款码
在商城请我一杯

继续读