最短路径 Shortest Path

最短路径 Shortest Path

加权有向图中每条路径都有值，其值是该路径上所有边的权值之和。最短路径 （Shortest Path）问题就是指求出两个给定顶点间权值最小的路径。

定义

两个顶点s和t之间的一条最短路径 是从s到t的一条有向简单路径，而且此路径 具有以下的性质：不存在另一条这样的路径且有更小的权值。

最短路径树（Shortest-path trees， 简称SPT）

给定一个图和一个指定的顶点s，则s的最短路径树是一个包含s以及由s可达的所有顶点的子图，它构成以s为根的一棵有向树，其中每条树路径都是图中的一条最短路径。最短路径树定义了从根到其它顶点的最短路径。

分类

图中最短路径问题主要是以下三类:

1. 源点－汇点最短路径
2. 单源最短路径
3. 全源最短路径

算法

求图中最短路径的算法常用的有：

1. Dijkstra算法
2. Floyd-Warshall算法
3. Bellman-Ford算法

###　基本操作

边松弛（edge relaxation）

检查一条给定的边，是否可以通过该边，对到其所指顶点的最短路径进行更新。

不妨设有条边e=(u,v)，它的长度是e.dist， d[i]表示源点到顶点i的最短距离，则松弛操作如下： if (d[v] > d[u] + e.dist) d[v] = d[u] + e.dist 上式的意思就是：如果从源点到u的最短距离加上u到v的长度小于当前源点到v的最短距离，那么更新源点到v的最短距离。 边松弛体现在Dijkstra算法和Bellman-Ford算法中

路径松弛（path relaxation）

检查一个给定顶点，是否可以使得连接另外两个给定顶点的最短路径进行更新。

不妨设现在有一个顶点x，还有另外两个顶点s和t。考虑能否通过x，使得s到t的最短距离变的更小，能的话，就进行路径松弛：if (d[s][t] > d[s][x] + d[x][t]) d[s][t] = d[s][x] + d[x][t]上式的意思是：如果s到x的最短距离加上x到t的最短距离小于s到t的最短距离，那么更新s到t的最短距离。路径松弛体现在Floyd-Warshall算法中。

Dijkstra算法

Dijkstra算法计算单源最短路径，它的基本思想：开始把源点放在SPT中，然后，每次增加一条边来构造SPT，所取的边总是可以给出从源点到尚未在SPT中的一个顶点的最短路径。也就是说，按照顶点与起始顶点的距离（通过SPT）为顺序来加入顶点。即：每次选不在SPT中距离源点最近的点加
入SPT。

具体步骤

1. 初始化：顶点集S只包含源点，即S={v}，顶点集U包含除v外的其他顶点。
2. 从U中选取一个顶点u，它是源点v到U中最短路径长度最小的顶点，然后把顶点u加入S中（此时求出了源点v到顶点u的最短路径长度）。
3. 以顶点u为新考虑的中间点，修改顶点u的出边邻接点j的最短路径长度，此时源点v到顶点j的最短路径有两条，即一条经过顶点u，一条不经过顶点u。
4. 重复步骤2和3，直到S包含所有的顶点即U为空。

基于堆的Dijkstra算法代码

struct Edge {
    int from, to, dist;
    Edge(int u, int v, int d) : from(u), to(v), dist(d) {}
};
struct HeapNode { 
    int d, u; // d表示该点到源点的距离，u是该点的编号
    bool operator< (const HeapNode& rhs) const {
        return d > rhs.d; 
    } // 小根堆
};
vector<Edge> edges; // edges存所有的边的信息
vector<int> G[MAXN]; // G[i]是顶点i发出的所有边
bool done[MAXN]; // 是否已经加入SPT
int d[MAXN]; // 每个点到源点的最短路径
int p[MAXN]; // 记录到顶点i的是哪条边
void Dijkstra(int s, int V) { // 计算所有顶点到顶点s的最短路径
    priority_queue<HeapNode> Q;
    for(int i = 0; i < V; ++i) d[i] = INF;
    d[s] = 0; // 顶点s做源点
    memset(done, 0, sizeof(done));
    Q.push((HeapNode){0, s});
    while (!Q.empty()) { 
        HeapNode x = Q.top(); Q.pop;
        int u = x.u; // 把出队的队头元素的标号给u
        if (done[u]) continue; // 已经在SPT中就跳过
        done[u] = true; // 标记u在SPT中了
        for (int i = 0; i < G[u].size(); ++i) { 
            Edge& e = edges[G[u][i]];
            if (d[e.to] > d[u] + e.dist) { 
                d[e.to] = d[u] + e.dist;
                p[e.to] = G[u][i];
                Q.push((HeapNode){d[e.to], e.to});
            }
        }
    }
}

注意

Dijkstra算法可以解决带有非负权值的单源最短路径问题，如果图中有负权值，则该算法不成立，因为它的前提是增加更多边时，路径的长度不会递减。

分析

利用优先队列实现的Dijkstra算法的时间复杂度是$O(ElogV)$，因为它是在一个规模最大是V的优先队列中进行V个插入，V个删除最小值，以及E个减少键值的操作。

Floyd-Warshall算法

Floyd-Warshall算法计算全源最短路径，它的本质是动态规划，用d[i][j][k]表示i到j的最短距离，而且该路径上的顶点的标号都小于等于k(除了源点和汇点)，那么下面的式子明显成立：d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1])

i到j中间标号最大是k的路径肯定是这样得到的：

1. i到j，而且中间标号最大是k-1的最短路径，或者
2. i到k，中间标号最大是k-1的最短路径加上了k到j，中间最大标号是k-1的最短路径。这两种情况里的小的就是要求的。

这样就有了$O(V^3)$的算法：

int d[MAXN][MAXN]; // 距离矩阵
int p[MAXN][MAXN]; // 路径数组
void FloydWarshall(int V) {
    // 初始化距离矩阵
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (i == j) {
                d[i][j] = 0; // 同一顶点的距离为0
            } else {
                d[i][j] = INF; // 不直接相连的顶点的距离设为无穷大
            }
            p[i][j] = -1; // 初始化路径数组
        }
    }

     // 根据边的信息更新距离矩阵
    for (int i = 0; i < edges.size(); ++i) {
        Edge& e = edges[i];
        if (d[e.from][e.to] > e.dist) {
            d[e.from][e.to] = e.dist;
            p[e.from][e.to] = e.from;
        }
    }
    
    // 计算最短路径
    for (int k = 0; k < V; ++k) {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (d[i][k] != INF && d[k][j] != INF && d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j]; // 更新最短路径
                    p[i][j] = p[k][j];
                }
            }
        }
    }
}

Bellman-Ford算法

Bellman-Ford算法计算单源的最短路径。

基本思路

为了计算一个从顶点s出发的最短路径，用d[i]表示源点s到i的最短路径，开始d[s] = 0，其它都是极大值，然后以任何顺序对每条边进行边松弛操作，完成V-1遍这样的操作，就可以得到各点到s的最短距离。

我们可以用一个FIFO队列来保存这些顶点，每一遍处理的时候只检查这些顶点发出的边，对于沿着一条发出边 进行松弛时可能有效的所有顶点都放在一 个队列中，每次从队列中取一个顶点，并沿着它的所有边进行松弛。如果其中任何 一条边导致到达某个顶点的一条更短的路径，那么将该点放入队列中。

基于FIFO队列的Bellman-Ford算法

bool bellman_ford(int a) { 
    queue<int> Q; // FIFO队列
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i) d[i] = INF;
    d[s] = 0;
    inq[s] = true; // inq[i] = true，表示顶点i在队列里
    Q.push(s);
    while (!Q.empty()) { 
        int u = Q.front(); Q.pop();
        inq[u] = false; //u出队了，就不在队列里了
        for (int i = 0; i < G[u].size(); i++) {
            Edge& e = edges[G[u][i]];
            if (d[u] < INF && d[e.to] > d[u] + e.dist) {
                d[e.to] = d[u] + e.dist;
                p[e.to] = G[u][i];
                if (!inq[e.to]) { // 如果e.to不在队列里才入队，否则，不用再入队 
                    Q.push(e.to); 
                    inq[e.to] = true;
                 if (++cnt[e.to] > n) return false; 
                }
            } 
        } 
    }
    return true;
}

负环

利用Bellman-Ford算法很容易来检查一个图是否存在负环。因为最多进行V-1遍所有边的松弛操作，所以V-1遍后看，是否有新的元素入队？有，就存在负环；否则，则没有。上述代码最后返回true就是无负环，返回false就是有负环。用FIFO队列不好判断哪些是一遍的操作，所以用了cnt数组，cnt[i]表示顶点i入队几次了，反正如果无负环，cnt[i]不会超过n，否则，最后必超过（可能是超过V-1遍操作后）。

Floyd_Warshall算法也能判断图中是否有负环，只要最后检查是否有d[i][i]是负的。上面程序最坏情况下运行时间仍和VE成正比，对于稠密图，运行时间可能不比Floyd好，对于稀疏图则最快可能快V倍。注意Floyd只能求所有的最短路径，不会因为你是求某点出发的最短路径而可以减少运行时间。实战中利用FIFO队列实现的Bellman-Ford算法效果相当好。

目前对于求有负环的最短路径是NP困难的。