前言

一。

---

3. 经典最短路算法

松弛

对于起点 $u$ 到终点 $v$，边权为 $w$。如果 $d_u+w<d_v$（$d_i$ 表示 $i$ 到起点的距离），则将 $d_v$ 更新为 $d_u+w$。这个过程就是松弛。

3 - 2. Dijkstra 单源最短路径

Dijkstra 其实就是 BFS + 贪心。每次找到到起点距离最短的点，进行拓展。但是实际上和 BFS 没什么关系。而且还和 Floyd 有点像。

朴素 Dijkstra

例如这张图：

• 设 $dis_i$ 为 $i$ 到起点的距离。初始化时 $dis$ 全为 不可达。将 $dis_1$ 设为 $0$。如图：

  

  然后，遍历与 $1$ 相连的点 $\{2,3\}$，对它们进行松弛。

  • $dis_2=\min(dis_2,dis_1+2)=\min(\inf,0+2)=2$。
  • $dis_3=\min(dis_3,dis_1+4)=\min(\inf,0+4)=4$。

• 然后，遍历 $dis$ 数组，找出 $dis$ 最小即到起点距离最小的点。$dis=\{0,2,4,\inf\}$，最小的是 $1$。但 $1$ 已经被使用过，所以松弛 $2$。

  • $dis_3=\min(dis_3,dis_2+1)=\min(4,2+1)=3$。
  • $dis_4=\min(dis_4,dis_2+5)=\min(\inf,2+5)=7$。

• $dis=\{0,2,3,7\}$。同时 $\{1,2\}$ 已经被使用过，所以松弛 $3$。

  • $dis_4=\min(dis_4,dis_3+2)=\min(7,3+2)=5$。

• 最后松弛 $4$ 点，但 $4$ 没有出边。Dijkstra 结束，最短路 $1 \to 4=5$。最后，$dis=\{0,2,3,5\}$。

这样，每次松弛遍历 $dis$ 数组里 $n$ 个点，松弛 $n$ 个点。时间复杂度 $O(n^2)$。

发现 Dijkstra 的计算量明显比 Floyd 少很多。代码：

void dij(int s)
{
	for (int i = 1; i <= n; ++i)
		dis[i] = INF;
	dis[s] = 0;
	for (int i = 1; i <= n; ++i)
	{
		int u = 0, t = INF;
		for (int j = 1; j <= n; ++j)
		{
			if (!vis[j] && dis[j] < t)
			{
				t = dis[j];
				u = j
			}
		}
		
		vis[u] = 1;
		for (auto nd : g[u])
		{
			int v = g[u].v, w = g[u].w;
			if (dis[u] + w < dis[v])
				dis[v] = dis[u] + w;
		}
	}
}

堆优化 Dijkstra

在朴素 Dijkstra 中，“找到距离最小的点”这个步骤可以使用一些能自动排序的数据结构来解决。优先队列（即堆，priority_queue）就是常用的一个。关于优先队列，可以看 这个。

如图：

开始时，$dis$ 全为不可达。将 $1$ 入队并将 $dis_1$ 设为 $0$。

将优先队列设为按照 $dis$ 从小到大排序。直接取出队列头上的那个节点，时间复杂度 $O(\log n)$。这里是 $1$。

弹出 $1$。遍历与 $1$ 相连的所有点 $\{2,3\}$，对它们进行松弛。这与朴素 Dijkstra 是一样的。

$dis_1+2<dis_2$，将 $2$ 入队。同理将 $3$ 入队。如果设置正确，优先队列会按 $dis$ 从小到大排序如下表：

priority_queue

dis	node
$2$	2
$4$	3

注意：priority_queue 默认是大根堆，即从大到小排序，具体见 这个。

每次都要拿出最短的点，时间 $\log n$。这进行 $n$ 次，因此总时间 $O(n\log n)$。
每条边都有可能进行入队操作，时间 $\log n$。这进行 $m$ 次，总时间 $O(m\log n)$。
综合就是 $O((n+m)\log n)$。代码：

void dij(int s)
{
	for (int i = 1; i <= n; ++i)
		dis[i] = INF;
	
	q.push({s, 0}); 
	dis[s] = 0;
	while (!q.empty())
	{
		int u = q.top().v;
		q.pop();
		if (vis[u])continue;
		
		vis[u] = 1;
		for (auto nd : g[u])
		{
			int v = nd.v, w = nd.w;
			if (dis[u] + w < dis[v])
			{
				dis[v] = dis[u] + w;
				q.push({v, dis[v]});
			}
		}
	}	
}

对比

正常情况下，如果 $m$ 和 $n$ 接近，$O((n+m)\log n)$ 可以看作 $n \log n$，相比朴素 $n^2$ 效率更高。

但堆优化也并非完全是优化。例如在这道题：P1186 玛丽卡 。当边数 $m$ 足够大时，“所谓堆优化其实是劣化”。此时用朴素 Dijkstra $O(n^2)$ 是更好的选择。

3 - 3. Bellman-Ford 单源最短路径

与 Floyd 和 Dijkstra 不同，Bellman-Ford 通过边来松弛。

例如这个图：

边：

$u$	$v$	$w$
1	2	$2$
	3	$4$
2		$1$
	4	$5$
3		$2$

遍历每一条边，通过 $u$ 松弛 $v$。即 $dis_v=\min(dis_v,dis_u+w)$。

初始时，如图（$dis_i$ 表示从起点到 $i$ 的最短路）：

1. 对于边 $(1,2,2)$：$dis_2=\min(dis_2,dis_1+2)=2$。
2. 对于边 $(1,3,4)$：$dis_3=\min(dis_3,dis_1+2)=4$。
3. 对于边 $(2,3,1)$：$dis_3=\min(dis_3,dis_2+1)=3$。
4. 对于边 $(2,4,5)$：$dis_4=\min(dis_4,dis_2+5)=7$。
5. 对于边 $(3,4,2)$：$dis_4=\min(dis_4,dis_3+2)=5$。

这确实是最好的情况，每次遍历边都能成功松弛，遍历完之后正是最短路。

但是实际上题目不会给出这么好的图的方式。例如：

边：

$u$	$v$	$w$
3	4	$2$
2	3	$1$
1	2	$2$
2	4	$5$
1	3	$4$

1. 对于边 $(3,4,2)$：两端都是 $\inf$，无法松弛。
2. 对于边 $(2,3,1)$：两端都是 $\inf$，无法松弛。
3. 对于边 $(1,2,2)$：$dis_2=\min(dis_2,dis_1+2)=2$。
4. 对于边 $(2,4,5)$：$dis_4=\min(dis_4,dis_2+5)=7$。
5. 对于边 $(1,3,4)$：$dis_3=\min(dis_3,dis+1+4)=4$。

这是正常情况。虽然图看上去一样，但边存储的顺序不一样结果就会不同。

为了保证求出最短路，这个过程要执行 $n$ 次（每次至少松弛 $1$ 个点，要松弛 $n$ 个点就是 $n$ 次）。这样才能求出最短路。时间复杂度：$O(nm)$。代码：

bool bell()
{
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	for (int i = 1; i <= n; ++i)
	{
		bool flag = 0;
		for (int j = 1; j <= m; ++j)
		{
			int v = g[j].v, u = g[j].u, w = g[j].w;
			if (i == n && dis[u] + w < dis[v])return 1;
			if (dis[u] + w < dis[v])
			{
				dis[v] = dis[u] + w;
				flag = 1;
			}
		}
		if (!flag)break;
	}
	return 0;
}

Bellman-Ford 的好处就是：代码简单（跟 Floyd 差不多），存图不需要用邻接矩阵或邻接链表等。只需要存储上面的表格那样的。

3 - 4. SPFA 单源最短路径

SPFA 其实算法思想上和 Bellman-Ford 是一致的。只是使用队列来优化。

在 Bellman-Ford 中，会有大量的边两端都是 $\inf$ 导致无法松弛。SPFA 就用队列解决了这个问题：将上一轮松弛成功的点入队。松弛后就出队。

例如这个图：

初始化 $dis$ 全为不可达，所有节点标记都为 未入队。将 $1$ 入队、将 $dis_1$ 设为 $0$ 并将 $1$ 标记为 入队。注意这个标记可以改为 未入队，即节点可以重复入队。

遍历与 $1$ 相连的点 $\{2,3\}$。同时弹出 $1$，将 $1$ 标记为 未入队。$dis_2=\min(dis2,dis_1+2)=2$，将 $2$ 入队，标记为 入队。节点 $3$ 同理。

等到队列为空，SPFA 结束。

理论上，时间复杂度是 $O(nm)$，实际上会快很多。但也会有一些数据能让 SPFA 退化为 $O(nm)$。代码：

bool spfa()
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(len, 0, sizeof(len));
    while (!q.empty())q.pop();
    
    q.push(1); vis[1] = 1;
    dis[1] = 0;

    while (!q.empty())
    {
        int u = q.front();
        q.pop(); vis[u] = 0;

        for (auto nd : g[u])
        {
            int v = nd.first, w = nd.second;
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                len[v] = len[u] + 1;
                if (len[v] >= n)return 1; // 判断负环
                if (!vis[v])
                {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    return 0;
}

3 - 3 & 4. 判断负环

负环：一个环，权值之和为负数。如果图中有负环，那就不存在最短路径。因为可以无限经过这个负环，让路径一直变小。

在没有负环的图中，最短路径最多经过所有点，即经过边数最长为 $n-1$。如果最短路径边数能达到 $n$，那一定存在负环。

• Bellman-Ford 判断负环：正常的 Bellman-Ford 外层只需要循环 $n-1$ 次（经过 $n-1$ 条边）。如果循环到第 $n$ 次还可以松弛，那一定存在负环。
• SPFA 判断负环：定义一个 $len_i$ 表示这条最短路径上的边数。$len_v=len_u+1$。如果 $len_v\ge n$，那一定存在负环。