之前在算法课的学习就总结了一下最短路径与最小生成树的区别，顺便提了一下思路，不过那时的最短路径只有常见的 Dijkstra 算法，现在对最短路径几种常见的算法进行补充。

最短路径：对任意给出的图 G(V, E) 和起点 S、终点 T，如何求出从 S → T 的最短路径。

本文具体介绍的算法有：Dijkstra、Bellman-Ford、SPFA、Floyd

Dijkstra

Dijkstra 是用来解决 单源最短路问题，它可以求出源点到其他所有顶点的最短路径，它的关键是贪心。

Dijkstra 只能解决所有边权都是非负数的情况，如果有负权边，要使用 SPFA

基本思路：

指定一个节点为初始点，将其看作一个 集合S ，剩余的点看作 另一个集合U
根据初始点，求出到其他点的距离 d[i]（若相邻，则为边的权值；若不相邻，则为 ∞ ）
选择最小的d[i]，并将其加入集合S，在U中去除它，暂时用x标记
再根据x，更新跟x相邻点y的d[y]的值： $d[y] = min{ d[y], d[x] + w[x][y] }$ ，则个操作有可能把距离调小，也有可能没变化，因而称为松弛操作
重复3，4两步操作，直至集合S包括所有的点，即集合U为空集时，求得初始点到其他所有点的最短路径

具体实现

集合 S 可以用一个bool 型数组 visited[] 来实现
dis[] 表示从起点 S 到达顶点 vi 的最短距离，初始化时除了起点 S 的 dis[S] = 0，其于顶点都赋为 INF（一个很大的数，可以是 0x3fffffff，防止 int 溢出)
pre[] 用来记录前趋结点，可以通过 DFS 的方式得到最短路径

伪代码：

dijkstra(G) {
	dis[]、visited[]、pre[] 初始化;
	for (循环 n 次) {
		u = 使 d[u] 最小且未访问的顶点标号;
		记 u 已访问;
		for (u 的所有邻居 v) {
			if (v 未访问 && 以 u 为中介使 s 到顶点 v 的最短距离 dis[v] 更优) {
				更新 dis[v];
                pre[v] = u;
            }
		}
	}
}

时间复杂度：邻接矩阵 $O(V^2)$ ，邻接表 $O(V^2 + E)$

获取最短路径：dfs(S, T)

void dfs(int s, int v) {
	if (s == v) {
		printf("%d\n", s);
		return;
	}
	dfs(s, pre[v]);
	printf("%d\n", v);
}

Bellman-Ford

Dijkstra 无法应用于负权图，为了解决负权边的最短路径问题，需要使用 Bellman-Ford 算法（简称 BF）。

Bellman-Ford 解决单源最短路径，与 Dijkstra 一样

基本思路

根据环中边的 权值和的正负 可以将环分为：零环、正环、负环。

零环、正环不会影响最短路径的求解，因为它们不能使最短路径更短
负环存在，且从源点可达，则会影响最短路径的求解

与 Dijkstra 相同，BF 设置了一个数组 dis[] 来记录源点到各个顶点的最短距离。

同时，BF 返回一个 bool 值：

如果存在 从源点可达的负环，则返回 false
否则，返回 true，此时 dis[] 存放的就是最短距离

如何判断是否存在 源点可达的负环：

首先对图中的边进行 V - 1 轮操作，每次都遍历图中所有边，进行松弛
如果没有源点可达的负环，则 dis[] 最优，即不能再松弛了，此时，再次遍历所有边，若任意一条可以松弛，则表示有源点可达的负环，返回 false
否则 dis[] 最优返回 true

证明

最短路径存在，则顶点个数肯定不超过 V 个。将源点 S 作为根生成 最短路径树（图和源点确定则唯一），因此树的层次一定不超过 V。而每次进行 BF 的一轮操作，树的会有一层确定，因此 BF 的松弛操作不会超过 V - 1 轮。

具体实现

由于 Bellman-Ford 需要遍历所有的边，因此使用邻接表更为方便
dis[] 表示从起点 S 到达顶点 vi 的最短距离，初始化时除了起点 S 的 dis[S] = 0，其于顶点都赋为 INF（一个很大的数，可以是 0x3fffffff，防止 int 溢出)
Bellman-Ford 会多次访问同一顶点，因此会重复统计最短路径数，因此需要将前驱数组设置为 set<int> pre[maxn]，遇到一条和已有最短路径长度相同的路径时，必须重新计算最短路径条数。

伪代码

BellmanFord(G){
	初始化;
    for (循环 n - 1 次){
        for (each edge u->v) {
            if (dis[u] + length[u->v] < dis[v]) {
                dis[v] = dis[u] + length[u->v];
                pre[v].clear();
                pre[v].insert(u);
            }
        }
    }
    for (each edge u->v) {
        if (dis[u] + length[u->v] < dis[v]) {
            return false;
        }
    }
    return true;
}

时间复杂度：邻接矩阵 $O(V^3)$ ，邻接表 $O(VE)$

SPFA

Bellman-Ford 的算法时间复杂度过高，因为多了很多无意义的操作，而更新 dis关键在于：只有当某个顶点 u 的 d[u] 改变时，它的邻居 d[v] 才有可能松弛。

由此可以进行优化：建立一个队列，每次将队首 u 取出，对 u 的邻居 v 进行松弛，若成功松弛且 v 未在队列中，则将其入队。终止条件：

队列为空，即不存在源点可达的负环
某个顶点的入队次数超过 V - 1 次，则存在源点可达的负环

这种优化后的算法称为 SPFA (Shortest Path Faster Algorithm)，期望时间复杂度 $O(kE)$

k 为一个常数，通常不超过 2，可见这个算法在大部分数据时异常高效，并且经常性地优于堆优化的 Dijkstra 算法
如果有负环，则退化为 $O(VE)$

具体实现

与 Bellman-Ford 一样，SPFA 使用邻接表更为高效
SPFA 需要一个 bool 数组 inq 来判断是否入队，也要新加一个计数数组来统计顶点入队次数

伪代码

SPFA(G) {
    初始化;
	queue<int> q;
    源点 s 入队;
    while (队列为空) {
        取出队首元素 u;
        for (u 的所有邻接边 u->v) {
            if (dis[u] + length[u->v] < dis[v]) {
                dis[v] = dis[u] + length[u->v];
                if (v 当前不在队列) {
                    v 入队;
                    if (v 入队次数大于 n - 1) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

优化：SLF (Small Label First)、LLL (Large Label Last)

Floyd

Floyd 算法用来解决 全源最短路问题，即对给定图 G(V, E)，求任意两点 u，v 之间的最短路径长度，时间复杂度为 $O(V^3)$ ，这个复杂度决定了 V 不能太大，因此使用邻接矩阵更为方便。

Floyd 的关键在于 动态规划：

将 d[k][i][j] 定义成：只能使用第1号到第k号点作为中间媒介时，点i到点j之间的最短路径长度。
- k 可以认为是 DP 在进行时的一种层次
状态转移方程： $d[k][i][j] = min(d[k-1][i][j],\ dp[k-1][i][k] + dp[k-1][k][j])$
由于上述状态转移只需要 k - 1 的状态，因此可以进行滚动数组优化： $d[i][j] = min(d[i][j],\ dp[i][k] + dp[k][j])$

具体实现

Floyd (G) {
    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]);
}