5.图论.题目3

题目

15.软件构造/BFS拓扑搜索

题目连接

概括来说，给出一个 有向图，把这个有向图转成线性的排序 就叫拓扑排序。当然拓扑排序也要检测这个有向图 是否有环，即存在循环依赖的情况，因为这种情况是不能做线性排序的。
实现拓扑排序的算法有两种：卡恩算法（BFS）和DFS；这题要使用卡恩算法（BFS）实现，这就类型广度优先搜索。
BFS算法代码：

#include <iostream>
#include "vector"
#include "queue"
#include "unordered_map"using namespace std;int main(){int m,n,s,t;cin>> n>> m;vector<int> indegree(n,0);unordered_map<int, vector<int>> graph;for(int i=0;i<m;i++){cin>> s>> t;graph[s].push_back(t);indegree[t]++;}queue<int> q;for(int i=0; i<n; i++){if(indegree[i]==0) q.push(i);}vector<int> res;// BFSwhile (!q.empty()){int cur = q.front();q.pop();res.push_back(cur);vector<int> files = graph[cur];if(!files.empty()){// cur有被依赖的文件for(int file : files) {indegree[file]--;if (indegree[file] == 0) q.push(file); // 将新的入度为0的节点放入que中}}}if(res.size() == n){for(int i=0;i<n-1;i++){cout<< res[i]<<" ";}cout<< res[n-1];}else cout<< -1<< endl;return 0;
}

---

16.参加科学大会/dijkstra 算法

题目链接

本题就是求最短路，最短路是图论中的经典问题即：给出一个有向图，一个起点，一个终点，问起点到终点的最短路径。这题可以使用dijkstra 算法解决。
dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法，需要注意两点：

• dijkstra算法可以同时求 起点到所有节点的最短路径
• 权值不能为负数
  

---

17.城市货物运输1/bellman_ford 算法

题目链接

解决经典的带负权值的单源最短路问题，此时就轮到Bellman_ford登场了。
共有两个关键点。

1. “松弛”究竟是个啥？
2. 为什么要对所有边松弛 n - 1 次 （n为节点个数） ？

B节点的mindist值可以由A，C节点值推导出来，状态一： minDist[A] + value 可以推出 minDist[B] 状态二： minDist[B]本身就有权值 （可能是其他边链接的节点B 例如节点C，以至于 minDist[B]记录了其他边到minDist[B]的权值）
如果 通过 A 到 B 这条边可以获得更短的到达B节点的路径，这就是松弛的概念；而在路径搜索中这成为剪枝操作；也是采用了动态规划的思想，即：将一个问题分解成多个决策阶段，通过状态之间的递归关系最后计算出全局最优解。

if (minDist[B] > minDist[A] + value) minDist[B] = minDist[A] + value

对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离；
节点数量为n，那么起点到终点，最多是 n-1 条边相连。那么无论图是什么样的，边是什么样的顺序，我们对所有边松弛 n-1 次 就一定能得到 起点到达 终点的最短距离。

普通版Bellman_ford算法

#include <iostream>
#include "vector"
#include "list"
#include "climits"using namespace std;struct Edge {int to;  // 链接的节点int val; // 边的权重Edge(int t, int w): to(t), val(w) {}  // 构造函数
};int main(){int m,n,p1,p2,val;cin>> n>> m;vector<vector<Edge>> graph(n+1); // 邻接表，但其实可以使用邻接矩阵进行存储图for(int i=0; i<m; i++){cin>> p1>> p2>> val;graph[p1].emplace_back(p2, val);}vector<int> mindist(n+1, INT_MAX);mindist[1]=0;// n-1次松弛for(int j=1; j<n; j++){// 遍历邻接表所有的边for(int i=1; i<=n; i++){for(auto &e: graph[i]){int from = i;int to = e.to;int price = e.val;if(mindist[from]!=INT_MAX && mindist[to]>mindist[from]+price) mindist[to] = mindist[from]+price;}}cout<< "松弛第 "<< j<< "次"<< endl;for(int k=1; k<=n; k++){cout<< mindist[k]<< " ";}cout<< endl;}if(mindist[n]==INT_MAX) cout<< "unconnected"<< endl;else cout<< mindist[n]<< endl;return 0;
}

队列优化版Bellman_ford算法
Bellman_ford 队列优化算法（Queue improved Bellman-Ford） ，也叫SPFA算法（Shortest Path Faster Algorithm）。大家可以发现 Bellman_ford 算法每次松弛 都是对所有边进行松弛。但真正有效的松弛，是基于已经计算过的节点在做的松弛。
基于以上思路，==如何记录上次松弛的时候更新过的节点呢？==用队列来记录。（其实用栈也行，对元素顺序没有要求）
基于队列优化的算法，要比bellman_ford 算法 减少很多无用的松弛情况，特别是对于边数众多的大图 优化效果明显

    while (!que.empty()) {int node = que.front(); que.pop();for (Edge edge : grid[node]) {int from = node;int to = edge.to;int value = edge.val;if (minDist[to] > minDist[from] + value) { // 开始松弛minDist[to] = minDist[from] + value;que.push(to);}}}

Bellman_ford队列优化版 的时间复杂度 并不稳定，效率高低依赖于图的结构;
例如 如果是一个双向图，且每一个节点和所有其他节点都相连的话，那么该算法的时间复杂度就接近于 Bellman_ford 的 O(N * E) N 为节点数量，E为边的数量。
所以如果图越稠密，则 SPFA的效率越接近与 Bellman_ford。反之，图越稀疏，SPFA的效率就越高。

---

18.城市运输货物2/bellman_ford 算法

题目链接
在17题的基础上，条件在评估从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本时，存在一种情况：图中可能出现负权回路。
负权回路是指一系列道路的总权值为负，这样的回路使得通过反复经过回路中的道路，理论上可以无限地减少总成本或无限地增加总收益。
为了避免在使用Bellman_ford算法遇到该情况时，出现这种异常情况，需要插入一个判断环节，返回这种异常情况。

在 bellman_ford 算法中，松弛 n-1 次所有的边 就可以求得 起点到任何节点的最短路径，松弛 n 次以上，minDist数组（记录起到到其他节点的最短距离）中的结果也不会有改变；而在有负权回路的情况下，一直都会有更短的最短路，所以 松弛 第n次，minDist数组也会发生改变。

那么很自然，我们在基础版的还是队列优化版的bellman_ford算法松弛n-1次的基础上，再额外松弛一次，判断mindist数组中是否发生改变，若有发生改变，则图中必定存在负权回路。

• 基础版bellman_ford：n个节点，最多n-1条边即可保证起点1至n连通，所以bellman_ford松弛n-1次即可得到到达n节点的距离最小路径。。在顶层for循环中增加一次for循环，在最后的循环中检查mindist数组是否满足松弛条件
• 队列优化版bellman_ford：在极端情况下，即：所有节点都与其他节点相连，每个节点的入度为 n-1 （n为节点数量），所以每个节点最多加入 n-1 次队列。在while循环下，检查松弛条件生效时，全局计数器数组对应节点下标加1，如果存在某节点加入队列次数超过 n-1次 就说明该图与负权回路。

以队列优化版Bellman_ford算法为例子：

#include <iostream>
#include "vector"
#include "queue"
#include "climits"using namespace std;struct Edge {int to;  // 链接的节点int val; // 边的权重Edge(int t, int w): to(t), val(w) {}  // 构造函数
};int main(){int m,n,p1,p2,val;cin>> n>> m;vector<vector<Edge>> graph(n+1); // 邻接表for(int i=0; i<m; i++){cin>> p1>> p2>> val;graph[p1].emplace_back(p2, val);}vector<int> mindist(n+1, INT_MAX);mindist[1]=0;queue<int> q; // 队列存放待遍历的节点q.push(1);vector<int> count(n+1, 0); // 记录每个节点的入队次数count[1]++;bool flag = false;while(!q.empty()){int node = q.front(); q.pop();for(auto edge: graph[node]){int from = node;int to = edge.to;int value = edge.val;if(mindist[to]>mindist[from]+value){mindist[to] = mindist[from]+value;q.push(to);count[to]++;if(count[to]==n) {flag = true;while(!q.empty()) q.pop(); //释放break;}}}}if(flag) cout<< "circle"<< endl;else if(mindist[n]==INT_MAX) cout<< "unconnected"<< endl;else cout<< mindist[n]<< endl;return 0;
}

---

19.城市运输货物3/bellman_ford 算法

题目链接
在17题的基础上，解决经典的带负权值的单源最短路问题，考虑最多经过 k 个城市的条件下，而不是一定经过k个城市，也可以经过的城市数量比k小，但要最短的路径。
最多经过k个节点，即最多经过k+1个节点到达终点的最短距离。此时在使用普通版的bellman_ford 算法时，处理带负权值回路的情况。

根据普通版代码每次顶层for循环遍历所有边可知，以上mindist是普通版bellman_ford算法得到第一次松弛的结果；所有边进行的第二次松弛，minDist数组为 ： -2 -2 -1 0 所有边进行的第三次松弛，minDist数组为 ： -3 -3 -2 -1等。
理论上来说，对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离。但我们在实际代码运行发现不仅仅 与起点一条边相连的节点更新了，所有节点都更新了。这说明至多经过k个节点这个限制没有起作用。因为理论上节点三最快在对所有边第二次松弛时，才会更新，而在第一次松弛时，当时是基于已经计算好的 节点2（minDist[2]）来做计算了。

所以在每次计算 minDist 时候，要基于 对所有边上一次松弛的 minDist 数值才行，所以我们要记录上一次松弛的minDist（直观的想法是每次顶层遍历时先拷贝上一次计算的结果）

    for (int i = 1; i <= k + 1; i++) {minDist_copy = minDist; // 获取上一次计算的结果for (vector<int> &side : grid) {int from = side[0];int to = side[1];int price = side[2];// 注意使用 minDist_copy 来计算 minDist if (minDist_copy[from] != INT_MAX && minDist[to] > minDist_copy[from] + price) {  minDist[to] = minDist_copy[from] + price;}}}

时间复杂度： O(K * E) , K为至多经过K个节点，E为图中边的数量；空间复杂度： O(N) ，即 minDist 数组所开辟的空间

本题本质
在之前17，18题没有使用mindist_copy拷贝上一次最小节点距离数组怎么会没有影。在17题，是没有负权回路的，那么无论比n-1多松弛多少次，mindist结果不会发生改变。因此在对所有边进行第一次松弛的时候，如果基于 本次计算的 minDist 来计算 minDist （相当于多做松弛了），也是对最终结果没影响。在18题，是判断是否有 负权回路，一旦有负权回路，则异常返回。
因此本题的关键区别是：
1.可以有负权回路，说明只要多做松弛，结果是会变的。
2.要求最多经过k个节点，对松弛次数是有限制的。

SPFA
要求最多经过k个节点，对松弛次数是有限制的。使用技巧，可以用一个变量 que_size 记录每一轮松弛入队列的所有节点数量；下一轮松弛的时候，就把队列里 que_size 个节点都弹出来，就是上一轮松弛入队列的节点。

    int que_size;while (k-- && !que.empty()) {minDist_copy = minDist; // 获取上一次计算的结果que_size = que.size(); // 记录上次入队列的节点个数while (que_size--) { // 上一轮松弛入队列的节点，这次对应的边都要做松弛int node = que.front(); que.pop();for (Edge edge : grid[node]) {int from = node;int to = edge.to;int price = edge.val;if (minDist[to] > minDist_copy[from] + price) {minDist[to] = minDist_copy[from] + price;que.push(to);}}}}

理论上，SPFA的时间复杂度不是要比 bellman_ford 更优吗？因为在该过程中queue的进出元素操纵，耗时很大，所以同的时间复杂度的情况下，SPFA 实际上更耗时了。

能否使用dijkstra算法？

此时最多经过2个节点的搜索就完毕了，但结果中minDist[7] （即节点7的结果）并没有被更；使用dijkstra算法所遍历的节点是1-->2-->3-->4，dijkstra每一步都采取贪心的策略，以最小的代价值到达下一个没访问的节点，因此没办法找到1-->2-->6-->7这条路径。

最短路径问题总结

至此已经讲解了四大最短路算法，分别是Dijkstra、Bellman_ford、SPFA 和 Floyd

注意：因为A * 属于启发式搜索，和上面最短路算法并不是一类，不适合一起对比，所以没有放在一起

大体使用场景的分析：

1. 如果遇到单源且边为正数的情况，直接Dijkstra 算法。至于 使用朴素版还是 堆优化版 还是取决于图的稠密度， 多少节点多少边算是稠密图，多少算是稀疏图，一般可以直接用堆优化版本。
2. 如果遇到单源边可为负数，直接 Bellman-Ford 算法，使用普通版还是队列优化版取决于图的稠密度
3. 如果是遇到多源点且边为正求最短路，直接 Floyd 算法。
4. 对于A * ，由于其高效性，所以在实际工程应用中使用最为广泛 ，由于其 结果的不唯一性，也就是可能是次短路的特性，一般不适合作为算法题