天天看点
返回

最短路问题（Floyd、Bellman-Ford算法、SPFA算法、Dijkstra算法）+打印路径

最短路问题分为两类：单源最短路和多源最短路。前者只需要求一个固定的起点到各个顶点的最短路径，后者则要求得出任意两个顶点之间的最短路径。我们先来看多源最短路问题。

Floyd算法 

int dist[400][400];
void Floyd(int n)
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

Floyd本质上是一个动态规划的思想，每一次循环更新经过前k个节点，i到j的最短路径。

这甚至不需要特意存图，因为dist数组本身就可以从邻接矩阵拓展而来。初始化的时候，我们把每个点到自己的距离设为0，每新增一条边，就把从这条边的起点到终点的距离设为此边的边权（类似于邻接矩阵）。其他距离初始化为INF（一个超过边权数据范围的大整数，注意防止溢出）。

//Floyd初始化
memset(dist, 63, sizeof(dist));
//利用memset的特性，先把所有距离初始化为0x3f3f3f3f
//注意这个数的两倍小于32位和64位机器上的INT_MAX
//因为memset是按位初始化的，63就是0x3f，会把int类型初始化为0x3f3f3f3f，即一个很大的整数。
for (int i = 1; i <= n; i++)
    dist[i][i] = 0;
for (int i = 0; i < m; i++)
{
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    dist[u][v] = w;
}

Floyd的时间复杂度显然是 O ( n 3 ) O(n^3) O(n3)，同时拥有 O ( n 2 ) O(n^2) O(n2) 的空间复杂度（n表示点数，m表示边数），都比较高，所以只适用于数据规模较小的情形。

一般而言，我们更关心的是单源最短路问题，因为当起点被固定下来后，我们可以使用更快的算法。

Bellman-Ford算法

因为起点被固定了，我们现在只需要一个一维数组dist[]来存储每个点到起点的距离。若1为起点，我们初始化时把dist[1]初始化为0，其他初始化为INF。

我们要找到从起点到某个点的最短路，设起点为S，终点为D，那这条最短路一定是S->P1->P2->…->D的形式，假设没有负权环，那这条路径上的点的总个数一定不大于n。

现在我们定义对点x, y的松弛操作是：

dist[y] = min(dist[y], dist[x] + e[x][y]);
//这里的e[x][y]表示x、y之间的距离，具体形式可能根据存图方法不同而改变

松弛操作就相当于考察能否经由x点使起点到y点的距离变短。

而Bellman-Ford算法实质就是：

把所有边松弛n-1遍！

这是种很暴力的算法，它的时间复杂度是 O ( n m ) O(nm) O(nm)。

void Bellman_Ford(int n, int m)
{
    for (int j = 0; j < n - 1; j++)
        for (int i = 1; i <= m; i++)
            dist[edges[i].to] = min(dist[edges[i].to], dist[edges[i].from] + edges[i].w);
            //松弛操作，n个点，m个边
}

这里用的是链式前向星存图，但是建议存的时候多存一个from，方便遍历所有边。当然其实并没什么必要，这里直接暴力存边集就可以了，因为这个算法并不关心每个点能连上哪些边。

我们之前说，我们不考虑负权环，但其实Bellman-Ford算法是可以很简单地处理负权环的，只需要再多对每条边松弛一遍，如果这次还有点被更新，就说明存在负权环。因为没有负权环时，最短路上的顶点数一定小于n，而存在负权环时，可以无数次地环绕这个环，最短路上的顶点数是无限的。

SPFA算法

O ( n m ) O(nm) O(nm)的复杂度显然还是太高了，现在我们想想，能不能别这么暴力，每次不松弛所有点，而只松弛可能更新的点？

我们观察发现，第一次松弛S, P1时，可能更新的点只可能是S能直接到达的点。然后下一次可能被更新的则是S能直接到达的点能直接到达的点。SPFA算法正是利用了这种思想。

SPFA算法，也就是队列优化的Bellman-Ford算法，维护一个队列。

据说随机数据下期望时间复杂度是 O ( n + log ⁡ n ) O(n+\log n) O(n+logn)。

总结一下，SPFA是如何做到“只更新可能更新的点”的？

  1. 只让当前点能到达的点入队
  2. 如果一个点已经在队列里，便不重复入队

  3. 如果一条边未被更新，那么它的终点不入队

    我们用一个inqueue[]数组来记录一个点是否在队列里，于是SPFA的代码如下：

void SPFA(int s)
{
    queue<int> Q;
    Q.push(s);
    while (!Q.empty())
    {
        int p = Q.front();
        Q.pop();
        inqueue[p] = 0;
        for (int e = head[p]; e != 0; e = edges[e].next)
        {
            int to = edges[e].to;
            if (dist[to] > dist[p] + edges[e].w)
            {
                dist[to] = dist[p] + edges[e].w;
                if (!inqueue[to])
                {
                    inqueue[to] = 1;
                    Q.push(to);
                }
            }
        }
    }
}

这个算法已经可以A掉洛谷P3371的单源最短路径（弱化版）了。然而它的时间复杂度不稳定，最坏情况可以被卡成Bellman-Ford，也就是 O ( n m ) O(nm) O(nm)。现在不少最短路的题会刻意卡SPFA，所以会有大佬说：SPFA死了。然而这仍然不失为一种比较好写、通常也比较快的算法。

SPFA也可以判负权环，我们可以用一个数组记录每个顶点进队的次数，当一个顶点进队n次时，就说明存在负权环。（这与Bellman-Ford判负权环的原理类似）

Dijkstra算法

下面介绍一种复杂度稳定的算法：Dijkstra算法。

Dij基于一种贪心的思想，我们假定有一张没有负边的图。首先，起点到起点的距离为0，这是没有疑问的。现在我们对起点和它能直接到达的所有点进行松弛。

因为没有负边，这时我们可以肯定，离起点最近的那个顶点的dist一定已经是最终结果。为什么？因为没有负边，所以不可能经由其他点，使起点到该点的距离变得更短。

那现在我们来考察2号点：

我们对2号点和它能到达的点进行松弛。这时dist保存的是起点直接到达或经由2号点到达每个点的最短距离。我们这时候取出未访问过的dist最小的点（即4号点），这个点的dist也不可能变得更短了（因为其他路径都至少要从起点直接到达、或者经由2号点到达另一个点，再从这另一个点到达4号点）。

继续这个流程，松弛4号点能到达的点：

然后分别考察3、5号点，直到所有点都被访问过即可。

总结一下，Dijkstra算法的流程就是，不断取出离顶点最近而没有被访问过的点，松弛它和它能到达的所有点。

如何取出离顶点最近的点？如果暴力寻找，那就是朴素的Dijkstra算法，时间复杂度是 O ( n 2 ) O(n^2) O(n2)，但我们可以采取堆优化。具体而言，我们可以用一个优先队列（或手写堆，那样更快）来维护所有节点。这样可以实现在 O ( m log ⁡ n ) O(m\log n) O(mlogn) 的时间内跑完最短路。

首先写一个结构体：

struct Polar{
    int dist, id;
    Polar(int dist, int id) : dist(dist), id(id){}
};

然后写一个仿函数（也可以用重载Polar的小于运算符代替），再构建优先队列：

struct cmp{
    bool operator ()(Polar a, Polar b){ // 重载()运算符，使其成为一个仿函数
        return a.dist > b.dist;    // 这里是大于，使得距离短的先出队
    }
};
priority_queue<Polar, vector<Polar>, cmp> Q;

Dijkstra算法的实现：

void Dij(int s)
{
    dist[s] = 0;
    Q.push(Polar(0, s));
    while (!Q.empty())
    {
        int p = Q.top().id;
        Q.pop();
        if (vis[p])
            continue;
        vis[p] = 1;
        for (int e = head[p]; e != 0; e = edges[e].next)
        {
            int to = edges[e].to;
            dist[to] = min(dist[to], dist[p] + edges[e].w);
            if (!vis[to])
                Q.push(Polar(dist[to], to));
        }
    }
}

当然，也有一种简化的写法，利用STL里的pair：

typedef pair<int, int> Pair;
priority_queue<Pair, vector<Pair>, greater<Pair> > Q;

这样的代码与原来只有三行的区别：

void Dij(int s)
{
    dist[s] = 0;
    Q.push(make_pair(0, s));
    while (!Q.empty())
    {
        int p = Q.top().second;
        Q.pop();
        if (vis[p])
            continue;
        vis[p] = 1;
        for (int e = head[p]; e != 0; e = edges[e].next)
        {
            int to = edges[e].to;
            dist[to] = min(dist[to], dist[p] + edges[e].w);
            if (!vis[to])
                Q.push(make_pair(dist[to], to));
        }
    }
}

但还是省去了写结构体和仿函数的步骤，因为pair已经内建了比较函数。

也许你会想，每个步骤不是应该取当前离源点最近、且未被访问过的元素吗，但我们现在每次让一个pair进入优先队列，这时pair里面存储的dist是那时该点到源点的距离，我怎么能保证每次取出来的点恰是离源点最近的点呢？

其实是这样的，在一个点被访问前，优先队列里会存储这个点被更新的整个历史。

注意：堆优化Dij虽然复杂度稳定且较低，但是不能处理负边。原因很明显，如果有负边，就不能保证离源点最近的那个点的dist不会被更新了。

打印路径

我们只需要用一个pre[]数组存储每个点的父节点即可。（单源最短路的起点是固定的，所以每条路有且仅有一个祖先节点，一步步溯源上去的路径是唯一的。相反，这里不能存子节点，因为从源点下去，有很多条最短路径）

每当更新一个点的dist时，顺便更新一下它的pre。这种方法对SPFA和Dij都适用，以下是对SPFA的修改：

if (edges[e].w + dist[p] < dist[to])
{
    pre[to] = p;    //在这里加一行
    dist[to] = edges[e].w + dist[p];
    if (!inqueue[to])
    {
        Q.push(to);
        inqueue[to] = 1;
    }
}

打印（以打印从1到4的最短路为例）：

int a = 4;
while (a != 1)
{
    printf("%d<-", a);
    a = pre[a];
}
printf("%d", a);

这样打印出的结果是反向的箭头，如果想得到正向的箭头，可以先将结果压入数组再逆序打印。

Dijstra实战题目讲解：

P3371 【模板】单源最短路径（弱化版）

P4779 【模板】单源最短路径（标准版）

最短路问题 算法 图论 dijkstra bellman–ford algorithm
上一篇: java最大流ford_Ford-Fulkerson 最大流算法
下一篇: 漫话最短路径（二）--bellman-Ford（贝尔曼-福特）算法

继续阅读