<style> .reveal table tr th ,.reveal table tr td{border-right:1px solid;border-left:none;} .reveal table:last-child tr th, .reveal table:last-child tr td{border-right:none;} </style> # 最短路算法 --- ## 几个概念 **路径**指图的一组顶点组成的序列，按照路径的方向，相邻顶点在图上是邻接的。 如果顶点和边都不重复出现，则称为 **简单路径**（simple path）。 如果起点和终点相同且没有其它重复的顶点和边，则称为 **环**（cycle）。 **多源最短路径**:给定一个图，求其中任意两个点之间的最短路径 --- ## 一、FLOYD算法 ---- floyd-warshall算法，是解决任意两点间最短路径的一种经典算法，可以正确处理**有向图或负权图**的最短路径问题，同时也可以被用于计算有向图的传递闭包。算法的时间复杂度为 $O(N^3)$，空间复杂度为 $O(N^2)$。 ---- 分析任意顶点x到y的最短距离d(x, y)，初始分为两种情况： - x能邻接到y，d(x, y) = w（边权） - x不邻接y，d(x, y) = $\infty$（无穷大） ---- 现在假设有一个顶点k，已经计算出d(x, k)和d(k, y)，也即发现了一条新路径 x -> k -> y，比较 d(x, k) + d(k, y) < d(x, y)，如果不等式成立就表示新的路径比原路径短，此时就可以更新 d(x, y) = d(x, k) + d(k, y)，这种做法称之为 **松弛**。 **松弛**过程就是对两点间路径求最短距离的过程，如果x到y的所有中间顶点都参加了"松弛"，则最后运算的d(x, y)就是最短路径。 依次类推，遍历图中所有的顶点k，将其它点按照以上x和y的分类，对d(x, y)进行松弛，最后就得到了任意两个顶点之间的最短路径。 ---- ### 4、松弛设计 用一个$n\times n$ 的矩阵`d[N][N]`存储任意两点之间的最短距离。 初始化： - `d[i][i] = 0` - `d[i][j] = w`(权),如果i邻接j - `d[i][j] =` $\infty$(无穷大)，如果i不邻接j ---- 循环每个顶点k，对每个经过k的路径“松弛”： - 理解：d(x, k)即为矩阵第k列的每个元素， d(k, y)即为矩阵第k行的每个元素， - 因此，循环第k列的每个元素`d[i][k]`，循环第k行的每个元素`d[k][j]`，两两相加对原最短路径进行松弛。 ```c if(d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j]; ``` ---- 每个顶点都这样松弛过之后，矩阵的每个元素即为任意两点间的最短距离。 `代码模板`： ```c++ for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(nt j=1; j<=n; j++) { if(d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j]; } ``` ---- ### 5、模拟过程 ||A |B |C | D |E | |:---|---|---|---|---|---| |A|||||| |B|||||| |C|||||| |D|||||| |E||||||  ---- | | A | B | C| D | E | |---| :------- | :--- | :--- | :--- | :--- | |A| 0 | 2 | $\infty$ | $\infty$ | 2 | |B| $\infty$ | 0 | 4 | 4 | $\infty$ | |C| $\infty$ | $\infty$ | 0 | 6 | $\infty$ | |D| $\infty$ | $\infty$ | $\infty$ | 0 | 8 | |E| $\infty$ | 10 | $\infty$ | $\infty$ | 0 | ---- 对顶点1，循环第一列的所有值 + 循环第一行的所有值，进行松弛判断: ```c++ if(d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j]; ``` 顶点1松弛结束，矩阵没有变化，因为顶点1没有进来的路径。 ---- 然后用顶点2进行松弛，下划线和红色的是被松弛的点： | | A | B | C| D | E | |---| :------- | :--- | :--- | :--- | :--- | |A| 0 | 2 | <u>6</u> | <u>6</u> | 2 | |B| $\infty$ | 0 | 4 | 4 | $\infty$ | |C| $\infty$ | $\infty$ | 0 | 6 | $\infty$ | |D| $\infty$ | $\infty$ | $\infty$ | 0 | 8 | |E| $\infty$ | 10 | $\color{red}{14}$ | $\color{red}{14}$ | 0 | ---- 与原始矩阵对照，可以看出松弛的过程： - 例如：`d[1][3]`原来不通，现在经过2中转，`d[1][2] + d[2][3]=6<`$\infty$，于是`d[1][3]->6` `提示`：有一个技巧叫十字交叉法，顶点2对应第二行、第二列，其它元素的值与横纵对应元素的和进行比较。 ---- 依次松弛下去，最后得到： | 0 | 2 | 6 | 6 | 2 | | :--- | :--- | :--- | :--- | :--- | | $\infty$ | 0 | 4 | 4 | 12 | | $\infty$ | 24 | 0 | 6 | 14 | | $\infty$ | 18 | 22 | 0 | 8 | | $\infty$ | 10 | 14 | 14 | 0 | ---- ### 6、应用要点 `回路`： 一般Floyd都应用与有向图，但也可用于无向图，但两者有一些区别。 核心在于回路，如果存在负回路，也即可以无限制走下去，每次路径都小于原路径，此时Floyd算法就会失真。 有向图的回路情况不多，而无向图肯定是回路，因此无向图基本要都是正边才好用此算法。 ---- `最大路`： 如果求最大路径，可把权设置为负的求最短路，最后再正回来。 `路径`： 如果要输出路径，可用path[i][j]来表示i->j最短路上j的前趋点，最后反向输出。 ---- ## 例题和练习 || |---| |[最短路径问题](http://39.99.183.126:8888/p/YBTJ1342)| |[牛的旅行](http://39.99.183.126:8888/p/YBTJ1343)| |[Jumping Takahashi 2](http://39.99.183.126:8888/p/abc257d)| |[frogger](http://39.99.183.126:8888/p/CCFPS04D09)| --- # 二、 Dijkstra（单源最短路） ---- ### 1、算法特点： 迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。 ---- ### 2、算法的思路 Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。 ---- 然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点， 然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。 然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。 ---- ### 3、Dijkstra算法示例演示 下面求下图，从顶点v1到其他各个顶点的最短路径  首先第一步，我们先声明一个dis数组，该数组初始化的值为： ||v1|v2|v3|v4|v5|v6| |---|---|---|---|---|---|---| |||||||| ---- 我们的顶点集T的初始化为：T={v1} 既然是求 v1顶点到其余各个顶点的最短路程，那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后，dis[2]（下标从0开始）的值就已经从“估计值”变为了“确定值”，即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。 为什么呢？因为目前离 v1顶点最近的是 v3顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短. ---- OK，既然确定了一个顶点的最短路径，下面我们就要根据这个新入的顶点V3会有出度，发现以v3 为弧尾的有： < v3,v4 >,那么我们看看路径：v1–v3–v4的长度是否比v1–v4短，其实这个已经是很明显的了，因为dis[3]代表的就是v1–v4的长度为无穷大，而v1–v3–v4的长度为：10+50=60，所以更新dis[3]的值,得到如下结果： 因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3]，通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过“边”来松弛v1顶点到其余各个顶点的路程。 ---- 然后，我们又从除dis[2]和dis[0]外的其他值中寻找最小值，发现dis[4]的值最小，通过之前是解释的原理，可以知道v1到v5的最短距离就是dis[4]的值，然后，我们把v5加入到集合T中，然后，考虑v5的出度是否会影响我们的数组dis的值，v5有两条出度：< v5,v4>和 < v5,v6>,然后我们发现：v1–v5–v4的长度为：50，而dis[3]的值为60，所以我们要更新dis[3]的值.另外，v1-v5-v6的长度为：90，而dis[5]为100，所以我们需要更新dis[5]的值。更新后的dis数组如下图： ---- 然后，继续从dis中选择未确定的顶点的值中选择一个最小的值，发现dis[3]的值是最小的，所以把v4加入到集合T中，此时集合T={v1,v3,v5,v4},然后，考虑v4的出度是否会影响我们的数组dis的值，v4有一条出度：< v4,v6>,然后我们发现：v1–v5–v4–v6的长度为：60，而dis[5]的值为90，所以我们要更新dis[5]的值，更新后的dis数组如下图： 然后，我们使用同样原理，分别确定了v6和v2的最短路径，最后dis的数组的值如下： ---- 因此，从图中，我们可以发现v1-v2的值为：∞，代表没有路径从v1到达v2。所以我们得到的最后的结果为： |序号|起点| 终点| 最短路径| 长度| | ---- | ---- | ---- | ---- | ---- | | 1 | v1 | v2 | 无 | ∞ | |2||v3| {v1,v3}| 10| |3||v4| {v1,v5,v4} | 50| |4||v5| {v1,v5} | 30 | |5||v6| {v1,v5,v4,v6}| 60| ---- 4、Dijkstra算法的代码实现（c++） ```c++ struct edge { int v, w; }; vector<edge> e[maxn]; int dis[maxn], vis[maxn]; void dijkstra(int n, int s) { memset(dis, 63, sizeof(dis)); dis[s] = 0; for (int i = 1; i <= n; i++) { int u = 0, mind = 0x3f3f3f3f; for (int j = 1; j <= n; j++) if (!vis[j] && dis[j] < mind) u = j, mind = dis[j]; vis[u] = true; for (auto ed : e[u]) { int v = ed.v, w = ed.w; if (dis[v] > dis[u] + w) dis[v] = dis[u] + w; } } } ``` 另一种实现 ```c++ // 邻接矩阵 typedef struct _graph { char vexs[MAX]; // 顶点集合 int vexnum; // 顶点数 int edgnum; // 边数 int matrix[MAX][MAX]; // 邻接矩阵 }Graph, *PGraph; // 边的结构体 typedef struct _EdgeData { char start; // 边的起点 char end; // 边的终点 int weight; // 边的权重 }EData; /* * Dijkstra最短路径。 * 即，统计图(G)中"顶点vs"到其它各个顶点的最短路径。 * * 参数说明： * G -- 图 * vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短路径。 * prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。 * dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短路径的长度。 */ void dijkstra(Graph G, int vs, int prev[], int dist[]) { int i,j,k; int min; int tmp; int flag[MAX]; // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。 // 初始化 for (i = 0; i < G.vexnum; i++) { flag[i] = 0; // 顶点i的最短路径还没获取到。 prev[i] = 0; // 顶点i的前驱顶点为0。 dist[i] = G.matrix[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。 } // 对"顶点vs"自身进行初始化 flag[vs] = 1; dist[vs] = 0; // 遍历G.vexnum-1次；每次找出一个顶点的最短路径。 for (i = 1; i < G.vexnum; i++) { // 寻找当前最小的路径； // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。 min = INF; for (j = 0; j < G.vexnum; j++) { if (flag[j]==0 && dist[j]<min) { min = dist[j]; k = j; } } // 标记"顶点k"为已经获取到最短路径 flag[k] = 1; // 修正当前最短路径和前驱顶点 // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。 for (j = 0; j < G.vexnum; j++) { tmp = (G.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); // 防止溢出 if (flag[j] == 0 && (tmp < dist[j]) ) { dist[j] = tmp; prev[j] = k; } } } // 打印dijkstra最短路径的结果 printf("dijkstra(%c): \n", G.vexs[vs]); for (i = 0; i < G.vexnum; i++) printf(" shortest(%c, %c)=%d\n", G.vexs[vs], G.vexs[i], dist[i]); } ``` ---- ## 优化（优先队列) ``` struct edge { int v, w; }; struct node { int dis, u; bool operator>(const node& a) const { return dis > a.dis; } }; vector<edge> e[maxn]; int dis[maxn], vis[maxn]; priority_queue<node, vector<node>, greater<node> > q; void dijkstra(int n, int s) { memset(dis, 63, sizeof(dis)); dis[s] = 0; q.push({0, s}); while (!q.empty()) { int u = q.top().u; q.pop(); if (vis[u]) continue; vis[u] = 1; for (auto ed : e[u]) { int v = ed.v, w = ed.w; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; q.push({dis[v], v}); } } } } ``` ---- ## 例题和练习 || |---| |[最短路径问题](http://39.99.183.126:8888/p/YBTJ1342)| |[最小花费](http://39.99.183.126:8888/p/CCFPS04E07)| |[城市路](http://39.99.183.126:8888/p/YBTJ1381) --- ## Bellman-Ford 算法 Bellman–Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。 求单源最短路 ---- ### Bellman–Ford 算法要用到的松弛操作 对于边 $(u,v)$，松弛操作对应下面的式子：$$dis(v) = \min(dis(v), dis(u) + w(u, v))$$ 这么做的含义是显然的：我们尝试用 $S \to u \to v$（其中 $S \to u$ 的路径取最短路）这条路径去更新 $v$ 点最短路的长度，如果这条路径更优，就进行更新。 ---- ## 过程 Bellman–Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。 每次循环是 $O(m)$ 的，那么最多会循环多少次呢？ 在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 $+1$，而最短路的边数最多为 $n-1$，因此整个算法最多执行 $n-1$ 轮松弛操作。故总时间复杂度为 $O(nm)$。 ---- 但还有一种情况，如果从 $S$ 点出发，抵达一个负环时，松弛操作会无休止地进行下去。注意到前面的论证中已经说明了，对于最短路存在的图，松弛操作最多只会执行 $n-1$ 轮，因此如果第 $n$ 轮循环时仍然存在能松弛的边，说明从 $S$ 点出发，能够抵达一个负环。 ---- ## 负环判断中存在的常见误区 需要注意的是，以 $S$ 点为源点跑 Bellman–Ford 算法时，如果没有给出存在负环的结果，只能说明从 $S$ 点出发不能抵达一个负环，而不能说明图上不存在负环。 因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行 Bellman–Ford 算法。 ---- ### 实现 ```cpp struct Edge { int u, v, w; }; vector<Edge> edge; int dis[MAXN], u, v, w; const int INF = 0x3f3f3f3f; bool bellmanford(int n, int s) { memset(dis, 0x3f, sizeof(dis)); dis[s] = 0; bool flag = false; // 判断一轮循环过程中是否发生松弛操作 for (int i = 1; i <= n; i++) { flag = false; for (int j = 0; j < edge.size(); j++) { u = edge[j].u, v = edge[j].v, w = edge[j].w; if (dis[u] == INF) continue; // 无穷大与常数加减仍然为无穷大 // 因此最短路长度为 INF 的点引出的边不可能发生松弛操作 if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; flag = true; } } // 没有可以松弛的边时就停止算法 if (!flag) { break; } } // 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环 return flag; } ``` ---- ## 例题与练习 |例题| |---| |[最短路径问题](http://39.99.183.126:8888/p/YBTJ1342)| --- ## SPFA算法 **算法介绍：** 　　SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。 ---- **算法流程：** 算法大致流程是用一个**队列**来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对**所有与他相邻的点**进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。 这个算法，简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法(只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作) ---- SPFA——Shortest Path Faster Algorithm，它可以在 $O(kE)$ 的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单： ---- 设 $Dis$ 代表 $S$ 到 $I$ 点的当前最短距离，$Fa$ 代表$S$ 到 $I$ 的当前最短路径中 $I$ 点之前的一个点的编号。开始时$Dis$ 全部为$+∞$，只有$Dis[S]=0$，$Fa$ 全部为 $0$。 维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点 $S$。用一个布尔数组记录每个点是否处在队列中。 ---- 每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断Dis[v]+len是否小于Dist[u]，若小于则改进Dis[u]，将Fa[u]记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。**若一个点入队次数超过n，则有负权环。** ---- SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的情况，k在2左右。 **在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。** ---- **代码实现：** ```c++ #include<iostream> #include<queue> #include<vector> #include<cstdio> #include<stack> using namespace std; #define MAX 50 #define INF 65535 typedef struct Edge{ int w; //边的权值 int end; //边的终点 }Edge; vector<Edge> e[MAX]; //动态数组模拟邻接链表存储 queue<int> que; //存储节点 int dist[MAX], pre[MAX]; bool in[MAX]; //标识是否在队列里面 int cnt[MAX]; //记录入队次数 int V, E; //顶点数和边数 int Init() { int st, end, weight; cin>>V>>E; for (int i=0; i < E; i++) { cin>>st>>end>>weight; Edge tmp; tmp.w = weight; tmp.end = end; e[st].push_back(tmp); //存入vector } for (int i=0; i< V; i++) { dist[i]= INF; cnt[i] = 0; in[i] = false; pre[i] = 0; } } bool SPFA(int st) { int i, v, end; dist[st] = 0; que.push(st); in[st] = true; cnt[st]++; while (!que.empty()) { v = que.front(); que.pop(); in[v] = false; for (i=0; i<e[v].size(); i++) { Edge t = e[v][i]; //取出邻接边 int end = t.end; //记录与v邻接的节点 if (dist[end] > dist[v] + t.w) //更新路径权值,v->end的权值为w { dist[end] = dist[v] + t.w; pre[end] = v; //记录前一个节点 } if (!in[end]) //不在队列里面 { que.push(end); in[end] = true; cnt[end]++; if (cnt[end] > V) //入队次数大于V次 { while (!que.empty()) //清空队列 { que.pop(); } return false; } } } } return true; } void ShowPath() { int i; stack<int> st; for (i=0; i<V; i++) { st.push(i); int tmp = pre[i]; while (tmp != 0) { st.push(tmp); tmp = pre[tmp]; } cout<<"1"; while (!st.empty()) { tmp = st.top(); st.pop(); cout<<"->"<<tmp+1; } cout<<" : "<<dist[i]<<endl; } } int main() { bool ret; freopen("input.txt", "r", stdin); Init(); ret = SPFA(0); ShowPath(); if (ret) cout<<"No Negative circle"<<endl; else cout<<"Exit Negative circle"<<endl; return 0; } ``` ---