最短路径问题相关算法

zhyjc6于2020-03-24发布 约6573字·约14分钟 本文总阅读量次

最短路径问题是图论中的经典问题，旨在寻找图中两结点的最短路径。该问题有以下几个变体：

最优子结构

最短路径算法通常依赖最短路径的一个重要性质：两个结点之间的一条最短路径包含着其它的最短路径。最优子结构是可以使用动态规划和贪心算法的一个重要指标。Floyd-Warshall算法就是动态规划算法，而Dijkstra算法则是贪心算法。

环路

一条最短路径是否可以包含环路？如果环路上的权重之和为负数，那么就不能包含该环路，因为不断遍历该环路就可以得到无限小的最短路径；如果环路上的权重之和为整数，那么最短路径也不可能包含该环路，因为目的地又不在换路上，为什么要去环路上绕一圈呢？这样得到的就不是最短路径了；而如果环路上的权重之和为0，那么最短路径是可以包含该环路的，但是没有什么意义。

松弛操作

对一条边（u, v）的松弛（relaxation）过程为：将从起点s到结点u之间的最短路径距离加上边（u,v）的权重，并与当前的s到v的最短路径估计进行比较，如果前者小，则更新s到v的最短路径。（我个人认为使用去松弛比较形象，因为s到v的最短路径被我们不断收紧）

Dijkstra算法

迪杰斯特拉算法(Dijkstra)是从起始点开始，采用贪心算法的策略，每次遍历到起始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。

总体思想

Dijkstra算法的总体思路就是依次获取 把起点到各个结点的最短路径升序排序 得到的最短路径序列。即首先计算所有最短路径中最短的那条，然后再计算次短的，……，最后才计算最短路径最长的那条。

为什么要这样呢？因为最短的最短路径就是起点的最近邻居啊（有向图是最近子节点）。假设起点为s，s的最近邻居为n1，那么s到n1的最短路径就得到了（就是边(s, n1)的权重）。接下来就是求次短最短路径了，会是距离s第2近的邻居吗？不一定！这时候我们需要以n1为中间结点、以其它没确定最短路径的结点为终点做松弛操作了（更新起点s到其它未确定最短路径的结点的距离），然后再在未确定最短路径的结点中，找到距离起点最近的那个，设为结点n2，没错，这里就是第二条最短路径了（可能是经过n1跳转的，也可能不是）。然后以n2为中间结点，其它未确定最短路径的结点为终点做松弛操作。……。就这样不断从未确定最短路径的结点中选出距离起点最近的结点nn确定最短路径，然后以nn为中间结点，除nn外其它未确定最短路径的结点为终点做松弛操作（更新起点到它们的距离），直到所有结点都确定最短路径。

算法步骤

  1. 初始时令 S={起点$V_0$}，T={其余顶点$V_i$}，与起点不相邻的结点初始化其与起点的距离为无穷大
  2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中
  3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从$V_0$到$V_i$的距离值缩短，则修改此距离值
  4. 重复上述步骤2、3，直到S中包含所有顶点为止

伪代码

//邻接矩阵表示图，起点为s,结点总数N
//int dist[u][v]表示结点u到v的距离，dist[i][i] = 0
//int visited[N]表示已确定最短路径的结点集合
for (int i = 0; i < N; i++) {//确定N-1条最短路径
	//在未确定最短路径的结点中找距离起点最近的结点dist[s][minindex] = mini;
    visited[minindex] = true;//找到后就确定了其最短路径,加入集合
    for (int j = 1; j <= N; j++) { //用刚刚确定的结点做松弛操作
        if (!visited[j] && dist[K][j] > dist[K][minindex]+dist[minindex][j]) {
            dist[K][j] = dist[K][minindex] + dist[minindex][j];
        }
    }
}
//此时dist[s][i]表示的就是起点s到结点i的最短路径了

时间复杂度

时间复杂度为$O(V^2)$，其中$V$是图中的顶点数量。

Bellman-Ford算法

对带有负权值边的图，迪杰斯特拉算法无法保障其正确性，而贝尔曼-福特（Bellman-Ford）算法却可以。它也是一种求单源最短路径问题的算法，原理是对图进行 V-1 次松弛操作，得到所有可能的最短路径。相比于迪杰斯特拉算法，它实现简单，但时间复杂度高，为$O(VE)$。

算法思想

贝尔曼-福特算法简单地对所有边进行松弛操作，共V-1 轮，其中V 是图中顶点的数量。在重复的计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。

判断负权回路

若图中存在负权回路，则不可能存在最短路径，因此需要检查是否存在负权回路。我们只需要将执行松弛操作的次数从V-1改为V，若不存在负权回路，则执行V-1次松弛操作就能找到所有最短路径，而第V次操作将全部失败。相反，若存在负权回路，则第V次操作中至少有一次会成功。

伪代码

procedure BellmanFord(list vertices, list edges, vertex source)
   // 该实现读入边和节点的列表，并向两个数组（distance和predecessor）中写入最短路径信息
 
   // 步骤1：初始化图
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null
 
   // 步骤2：重复对每一条边进行松弛操作
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u
 
   // 步骤3：检查负权环路
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]
           error "图包含了负权环"

时间复杂度

最外层的for循环语句会执行V次（加上检查负权环路），而内层会遍历所有边，所以会执行E次。最终整个时间复杂度为$O(VE)$，其中V是顶点数，E是边数。

SPFA算法

SPFA(Shortest Path Faster Algorithm，外文名Bellman-Ford using queue optimization) 算法是 Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判断是否含有负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 $O(VE)$。

为了避免最坏情况的出现，在正权图上应使用效率更高的Dijkstra算法。若给定的图存在负权边，类似Dijkstra算法等算法便没有了用武之地，SPFA算法便派上用场了。

算法思想

该算法其实是贝尔曼-福特（Bellman-Ford）算法的队列优化版。Ford算法是对所有边进行V-1轮的松弛操作，但是很有可能第一轮只有少数的边更新了，大部分的边的权值都没有更新（这里的边都指的是起点到某一点的边，下同），这时第二轮的松弛操作的对象还是全体边，那么对于没有更新的那部分边来说就是在做无用功。因为第二轮更新的边只有可能是上一轮更新的边及其邻边。而SPFA算法就是只提取有更新的边，将其放入队列等待处理，每次从队首取出一个结点，对其子节点（或邻居）做松弛操作。这样就避免了大量的无用功操作。

算法步骤

用数组d记录从起点到每个结点的最短路径估计值，而且用邻接链表dist来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

只要最短路径存在，上述SPFA算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。

伪代码

//邻接链表表示图，起点为s,结点总数N
vector<vector<pair<int,int>>> dist(N+1);
//dist[u]表示从结点u出发的下一个结点及其权重的集合{v,w}
//d[i]表示起点s到i的最短路径
//inQue[i]=true表示结点i正在队列中

queue<int> que;//起点入队，先进先出队列
while (!que.empty()) {
    int u = que.front(); que.pop();//队首出队
    inQue[u] = false;
    for (auto &v_w : dist[u]) {//对结点u的每一个邻居结点及其权重
        if (d[v_w.first] > d[u] + v_w.second) {//做松弛操作
            d[v_w.first] = d[u] + v_w.second;
            if (!inQue[v_w.first]) {//如果权值更新了并且不在队列中则将其加入队列
                que.push(v_w.first);
                inQue[v_w.first] = true;
            } 
        }
    }
}

优化策略

SPFA算法有两个优化策略SLF和LLL：

SLF 和 LLF 在随机数据上表现优秀，但是在正权图上最坏情况为 $O(VE)$，在负权图上最坏情况为达到指数级复杂度。

Floyd-Warshall算法

弗洛伊德算法（Floyd(Floyd-Warshall)）是一种利用动态规划的思想寻找给定的加权图中任意两点之间最短路径的算法。代码很简洁很优雅（核心代码只有4行）：

本质上是动态规划思想，其状态转移方程为：

\[dist[i,j]=min\{dist[i,k]+dist[k,j], dist[i,j]\}；\]

$dist[i,j]$表示结点 i 到 j 的最短路径值，k 是用于为 i、j 做松弛操作的中间结点。

算法思想

该算法是求任意两点之间的最短距离，因此我们以除该两点外的其它结点为中点结点，对该两个结点做松弛操作。但是我们不能一次性地使用其它结点为这两个结点做松弛操作，而是以一个结点为中点，对其它任意两个结点做松弛操作。使得所有的两个结点之间的距离逐渐趋向于最短路径。

算法步骤

伪代码

int V;//顶点个数
//邻接矩阵法表示图
//dist[u][v]表示顶点u到v的边的权值，若没有边则取最大值
//dist[i][i] = 0
int dist[V][V];

void floyd() {
	for (int k = 0; k < V; k++) { //对于除k外的所有边，以k为中心点做松弛操作
		for (int i = 0; i < V; i++) {
			for (int j = 0; j < V; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
			}
		}
	}
}

复杂度

其运行时间为$\Theta(V^3)$，隐藏的常数系数比较小，因此对于中等规模及以下的图，该算法效率相当好。

构建最短路径

为了计算两个结点之间的最短路径，我们需要将成对结点u和v最后一次更新dist[u][v]时的k值保存起来，假设保存的k值为w，那么经过w结点后，dist[u][v]的值变为最小，得到最短路径。由于该路径经过了结点w，那么我们就可以递归调用的方式找到 u 到 w 的最短路径和 w 到 v 的最短路径，最后再将这两条路径相加就得到了 u 到 v 的最短路径了。

伪代码

int V;//顶点个数
//邻接矩阵法表示图
//dist[u][v]表示顶点u到v的边的权值，若没有边则取最大值
//dist[i][i] = 0
int dist[V][V];
//via[u][v]保存u到v的最短路径中间结点的最大结点（最后一次松弛操作的中心结点）
//初始化为-1
int via[V][V];

void floyd() {
	for (int k = 0; k < V; k++) { //对于除k外的所有边，以k为中心点做松弛操作
		for (int i = 0; i < V; i++) {
			for (int j = 0; j < V; j++) {
                via[i][j] = k;
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
			}
		}
	}
}

//计算u到v的最短路径，并保存到path
void build(int u, int v, vector<int>& path) {
	if (via[u][v] == -1) {//说明u到v的最短路径没有中间结点，就是u->v
    	path.push_back(u);
        if (u!=v) path.push_back(v);
    } else {
    	int w = via[u][v];//最大中间结点
        build(u, w, path);
        path.pop_back(w);//两个w,需要删除一个
        build(w, v, path);
    }
}

参考资料