最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

单源最短路

即对确定的源点（起点），求它到其它所有可达的点的最短路径。对于单源最短路算法，又可以分为处理正权边图和带负权边图的两种。

正权图——Dijkstra算法

个人认为对Dijkstra算法的一个很形象的描述是：将边看作一条条水渠，边的权为水渠的长度(m)。在源点处倒入水，假设水的速度恒定为1m/s，那么当水首次流到顶点X时，所经过的时间就是源点到X的最短路径长度。

以下图举例：

假设从A倒入水，水四散向每个可能的方向流出。那么水流首先会到达B顶点，这也是水流第一次经过B顶点，所以A-B的最短路径长度即为1。类似的，我们可以得出水流依次经过的顶点顺序为A -> B -> C -> D -> D，其中D取第一次经过时的时间，也就是9。

Dijkstra算法的思想基本如此，但抽象为计算机语言却有些不同，接下来讲讲Dijkstra算法的实现过程。

将顶点编号为1~n
维护一个数组dist， dist[i]表示目前顶点i和源点的最短路径长度，开始时dist初始化为正无穷，而源点的dist设为0, 表示当前只知道源点到源点的路径长度为0.

整个Dijkstra算法就是基于bfs以及贪心对dist数组更新的一个过程。

在算法中重复执行此过程：取出目前未遍历过且dist最小的一个顶点，更新其所有指向的顶点的dist

例如以此图举例

第一次： dist[A] = 0，其它都为正无穷，因此遍历A结点，并更新A指向的所有结点的dist

更新完毕后dist[B] = 1, dist[C] = 5, dist[D] = 10.

第二次：取出B顶点遍历， dist[D] = min (dist[D], dist[B] + weight(B -> D)) （这一步也叫做松弛操作)，所以dist[D]被更新为9

以此类推。

以不严谨的角度，可以稍微解释下Dijkstra算法的正确性：每次都只选择dist最小的顶点，是因为dist更大的顶点可能被dist小的顶点再加一段路径而更新掉，而最小的dist在没有负权边的情况下必然是最短路径。

在代码实现上，由选择dist最小顶点的手段的不同可以分为朴素Dijkstra和堆优化Dijkstra

朴素Dijkstra

朴素版本的Dijkstra在选择顶点时，采用的方式是直接遍历dist数组，而选出未被遍历过且dist最小的顶点。

每次选择至少都会确定一个顶点的最短路径，所以至多要选择n次；而每次选择的过程中都要遍历一次dist数组，因此时间复杂度为

int n, m, g[N][N];
int vis[N], dist[N];

void dijkstra (int src) {
    memset(dist, 0x3f, sizeof dist);
    dist[src] = 0;
    for (int i = 1; i <= n; i ++) {
        int t = -1;
        for (int j = 1; j <= n;  j++) {
            if (!vis[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }
        vis[t] = 1;
        for (int j = 1; j <= n; j ++) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
}

堆优化Dijkstra

前面提到过Dijkstra本质上可以看成一个bfs的过程，但bfs下次要遍历的顶点并不像普通的bfs那样随意，而是要选择dist最小的顶点。我们可以用优先队列(小根堆)来实现这一过程，每次选择时，直接取出堆顶元素，然后更新dist并把被更新过的顶点及其dist加入优先队列。

int h[N], e[M], ne[M], w[M], idx;
int vis[N], dist[N], n, m;

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra (int src) {
    memset(dist, 0x3f, sizeof dist);
    dist[src] = 0;
    priority_queue<pii, vector<pii>, greater<>> heap;
    heap.push({0, src});
    while (heap.size()) {//以堆被清空为结束标志
        auto [v, x] = heap.top(); heap.pop();
        if (vis[x]) {//已被遍历过， 直接跳过
            continue;
        }
        vis[x] = true;
        for (int i = h[x], j = e[i]; i != -1; i = ne[i], j = e[i]) {
            if (v + w[i] < dist[j]) {//被更新
                dist[j] = v + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

优先队列让取出dist最小的顶点能以O(1)的代价实现，但每次取出后的调整为O()，遍历所有边为O()，因此时间复杂度为

两种实现方式的适用场景

虽然堆优化Dijkstra的时间复杂度看上去比朴素算法更优秀，但堆优化的时间会受到边数的影响，当边数与顶点数的平方为一个量级时，堆优化的时间和空间开销都不乐观。

所以一般的，当图为稠密图时（m 与 n²同一个量级), 使用邻接矩阵存储，朴素Dijkstra；当图为稀疏图时(m远小于n²)，使用邻接表存储，堆优化Dijkstra.

负权图最短路

前面提到， dijkstra是不能处理带负权边的图的，因为这会导致dijkstra算法最根本的贪心思想不再正确——当dist[i]最小时， dist[i]不一定是源点到i的最短路径，因为dist[i]可能大于dist[j] + 某个负数。

Bellman-Ford算法

Bellman-Ford算法(以下简称BF算法)基于动态规划的思想，与Dijkstra类似的是， BF算法同样维护最短路径长度数组dist。不同的是， Dijkstra使用贪心思想，选取目前dist最小的顶点，并遍历其所有出边来更新dist数组；而BF算法则是直接在每次循环过程中遍历整个边集，来达到更新dist数组的目的。

即对于每一条边[src, dest, weight]，都取出来并执行松弛操作：dist[dest] = min(dist[dest], weight + dist[src])

假设顶点A到顶点B的最短路径中有k条边，则k小于等于n-1；显然可以发现的是，每次遍历边集都至少更新A到B路径中的一条边为最短路径，所以至多需要遍历n-1次。

设边的数量为m，则BF算法的时间复杂度为。

因为BF算法只需要遍历边集，所以存储图的时候可以只建立一个边集数组。

struct edge {
    int a, b, w;
} edges[N];
int dist[N], n, m;

void bllman_ford (int src) {
    memset(dist, 0x3f, sizeof dist);
    dist[src] = 0;
    for (int i = 1; i < n; i ++) {
        for (int j = 1; j <= m; j ++) {
            auto [a, b, w] = edges[j];
            dist[b] = min(dist[b], dist[a] + w);
        }
    }
}

SPFA(队列优化Bellman-Ford)

BF算法的时间复杂度为，在一般的图中m都是远大于n, 如此看来BF虽然能处理负权边，但效率却远低于dijkstra。

BF的效率低在了哪里？显然是每次都遍历整个边集数组，但其实其中真正的更新了dist的边却不多。

SPFA正是对BF算法这个痛点进行了优化。 "SPFA"，即Shortest Path Faster Algorithm，从名字上也能看出大家对其效率上的认可。

SPFA基于这样一个事实：对于边[src, dest, weight]，只有当dist[src]发生改变后，该边才可能用于更新dist[dest]，这就是说只有dist发生改变的顶点的出边才有被遍历的价值。这一点与Dijkstra算法不谋而合，所以SPFA与Dijkstra算法在形式上是类似的。

对于SPFA是实现细节，特别要提的一点是st数组，在这里st[i]用于标记顶点i是否在队列中，以免顶点重复入队，这显然是没用意义的。

SPFA的复杂度并不稳定，对于一般数据，它要比朴素BF快得多，甚至能以同样的时间处理正权图；但对于针对型数据，复杂度最坏能退化到和BF一样的。

int h[N], e[M], ne[M], w[M], idx;
int st[N], dist[N], n, m;

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa (int src) {
    queue<int> q;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0, q.push(1);
    
    while (q.size()) {
        int u = q.front();
        q.pop();
        st[u] = false;
        for (int i = h[u], j = e[i]; i != -1; i = ne[i], j = e[i]) {
            if (dist[j] > dist[u] + w[i]) {
                dist[j] = dist[u] + w[i];
                if (!st[j]) {
                    q.push(j), st[j] = true;
                }
            }
        }
    }
}

BF和SPFA的其它应用

BF求解有边数限制的最短路径

在BF算法那里我们提到，假设1~n的最短路径中有k条边，那么每次遍历边集都至少可以更新它的一条边。为什么是“至少”呢？这是因为在遍历边集的途中边的更新可能发生串联，如A->B->C，如果先遍历了A->B再遍历B->C，则一次遍历就更新了两条边，反之只能更新A->B这一条边。

我们可以使用一些手段，使得每次遍历边集都只能更新一条边，那么若只循环k次，则边数大于k的最短路径将不能被发现。

这个手段就是，在每次遍历边集前，将dist数组拷贝一份为backup，使用上一次的dist数组来更新当前的dist数组，这就可以避免串联。

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

int dist[N], n, m, k, backup[N];

void bllman_ford (int src) {
    memset(dist, 0x3f, sizeof dist);
    dist[src] = 0;
    for (int i = 1; i <= k; i ++) {
        memcpy(backup, dist, sizeof dist);
        for (int j = 1; j <= m; j ++) {
            auto [a, b, w] = edges[j];
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
}

SPFA判断负环

普通的SPFA是不能处理带负环的图的，否则会陷入死循环；但是我们可以通过记录额外信息来判断图中是否出现负环。

记录cnt[i]为当前i顶点到源点最短路径中的边数，若cnt[i] >= n，则显然存在负环。

要注意的点是，由于图可能并不连通，因此初始时要把所有顶点入队；在这里并不是为了求最短路，所以dist可以不初始化，只需要保证初始全部相同即可。

int h[N], e[M], ne[M], w[M], idx;
int st[N], dist[N], cnt[N], n, m;

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa () {
    queue<int> q;
    for (int i = 1; i <= n; i ++) {
        q.push(i), st[i] = true;
    }
    
    while (q.size()) {
        int u = q.front();
        q.pop();
        st[u] = false;
        for (int i = h[u], j = e[i]; i != -1; i = ne[i], j = e[i]) {
            if (dist[j] > dist[u] + w[i]) {
                dist[j] = dist[u] + w[i], cnt[j] = 1 + cnt[u];
                if (cnt[j] == n) {
                    return true;
                }
                if (!st[j]) {
                    q.push(j), st[j] = true;
                }
            }
        }
    }
    return false;
}

多源最短路

多源最短路，也叫做全局最短路，即求出图中任意两个点的最短路径。

Floyd-Warshell算法

Floyd-Warshall算法（英语：Floyd-Warshall algorithm），中文亦称弗洛伊德算法或佛洛依德算法[1]，是解决任意两点间的最短路径的一种算法[2]，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包[3]。

F-W算法基于动态规划，它依赖于这样一个事实：若i到j的最短路径为dist[i][j]，则对于任意顶点k， dist[i][k] + dist[k][j] >= dist[i][j]。反之dist[i][j]就不为最短路径，应更新为dist[i][k] + dist[k][j]。

动态规划的思想如下：

使用三维数组f[k][i][j]表示路径中(除源点和汇点)只出现过前k个顶点时， i顶点到j顶点的最短路径
当考虑f[k][i][j]时，可分为两种情况： i->j最短路径不经过k顶点，即f[k-1][i][j]; 经过k顶点，即f[k - 1][i][k] + f[k - 1][k][j]。所以状态转移方程为：

可以发现， f[k]只与f[k-1]相关，所以只需要用二维数组存储每次迭代完的状态, 然后在上一次迭代的基础上进行状态转移。

对应到图的存储，只需要用邻接矩阵存储图，然后在矩阵中进行递推即可。

int g[N][N], n;

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]);
}