最短路问题

いつの日かdistanceも

抱きしめられるようになれるよ

---

问题分类

单源最短路

从一个点到其他所有点的最短距离

• 不存在负权边

1. 朴素Dijkstra算法 $O(n^2)$
2. 堆优化版的Dijkstra算法 $O(m\log n)$

• 存在负权边

1. Bellman-Ford算法 $O(nm)$
2. SPFA $一般O(m)，最坏O(nm)$

多源汇最短路

有多个起点到不同点的最短距离

• Floyd算法 $O(n^3)$

模板

Dijkstra算法

适用于无负权边的图。可以有重边或自环。

算法思想

• 定义一个distance[]数组，distance[i]表示从起点到点i的距离。
• 将distance[]初始化，distance[1] = 0，表示起点到自己的距离为0。其余全部赋值为INF，表示还未找到最短距离。
• 定义一个集合st[]，每当找到一个点i到起点的最短路时，st[i] = true，将点i加入集合中。
• 迭代n次，每次搜索所有未加入集合中的点，从中找到distance最小的那个点t，将其加入集合中。然后更新distance[]，判断t加入路径之后经过t的新路径距离是否小于原路径。

朴素Dijkstra

Dijkstra求最短路 I
不使用任何数据结构进行维护，时间复杂度为$O(n^2)$，适用于稠密图。

实现

const int N = 510;

int n, m;
int g[N][N];  // 邻接矩阵存图
int dist[N];
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
        {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
            {
                t = j;
            }
        }
        st[t] = true;

        for (int j = 1; j <= n; j++)
        {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }

    if (dist[n] == 0x3f3f3f3f)
        return -1;
    else
        return dist[n];
}

堆优化的Dijkstra

Dijkstra求最短路 II
用堆存储所有点到起点的距离，这样每次找distance最小的那个点t的时间复杂度就是$O(1)$ ，而更新其他点的距离的操作变为$O(\log n)$。本题中点和边数均为$10^5$，所以是稀疏图，用邻接表来存。

实现

typedef pair<int, int> PII;
const int N = 150010;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];
int n, m;

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.first, distance = t.second;
        if (st[ver])
            continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f)
        return -1;
    return dist[n];
}

Bellman-Ford算法

有边数限制的最短路
Bellman-Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。适用于有边数限制、有负权边的图。可以用来判断是否有负环。

通常来说，SPFA在各方面都比Bellman-Ford更优。但是如果题中限制了最短路的边数，则只能用Bellman-Ford。

算法思想

非常的简单
松弛：对于边$(u, v)$，松弛操作对应下面的式子$dist(v)=\min(dist(v),dist(u)+w(u,v)$
也就是如果从源点直接到$v$点的距离大于从源点先到$u$ 再到 $v$，则将最短路从源->v 更新为 源->u->v

对于有 $n$ 个点， $m$ 条边的图，进行 $n - 1$ 次迭代，每次迭代对所有边进行松弛。直到没有边能够松弛了，算法结束。
如果松弛次数大于 $n-1$ ，说明图中有负环（因为一共只有 $n$ 个点，任意两个点之间最多有 $n-1$ 条边）。
所以，如果我们想知道是否存在源点到目标点的边数最大为 $k$ 的最短路径，则只要进行 $k$ 次迭代。
伪代码如下：

for n
	for 所有边 a,b,w 
		dist[b] = min(dist[b],back[a] + w)

实现

const int N = 510, M = 10010;
int n, m, k;
int dist[N];
int back[N];  // 因为每次迭代都会松弛所有边，可能会导致串联，所以使用一个备份，其中存的是上一次迭代的dist

struct {
    int a, b, w;
}edges[M];

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < k; i++)
    {
        memcpy(back, dist, sizeof dist);
        for (int j = 0; j < m; j++)
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], back[a] + w);
        }
    }
}

SPFA

spfa求最短路
spfa判断负环

算法思想

spfa是队列优化后的Bellman-Ford。在Bellman-Ford算法中，每一次迭代都会搜索所有的边，判断是否需要松弛。然而很显然，只有在上一轮迭代中松驰过的边才有可能需要松弛，而其他的边在上一轮是没有发生改变的。
所以我们使用一个队列来维护那些可能需要松弛的结点，就不需要每次都访问所有点了。

实现

const int N = 100010;
int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true; // st用来标记某个点是否进入队列

    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

Floyd算法

Floyd求最短路
适用于任何图，可以有负权边。但不能有负环。

算法思想

基于高深的动态规划。
首先图要用邻接矩阵来存。
定义一个数组 g[k][x][y] ，表示 $x$ 只经过 $1, 2 \dots k$ 到 $y$ 的最短距离。所以 g[n][x][y] 就是 $x$ 到 $y$ 的最短距离。所以进行 $n$ 次迭代，每次 g[k][x][y] = min(g[k - 1][x][y], g[k - 1][x][k] + g[k - 1][k][y] 。而实际上，数组的第一维对结果无影响，所以可以省略。

实现

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