手机设置管理网站首页,wordpress 4.7下载,网站开发的论文怎么写,阿里企业邮箱注册申请免费一、dijkstra#xff08;朴素版#xff09;精讲
47. 参加科学大会
思路
本题就是求最短路#xff0c;最短路是图论中的经典问题即#xff1a;给出一个有向图#xff0c;一个起点#xff0c;一个终点#xff0c;问起点到终点的最短路径。
接下来讲解最短路算法中的 d…一、dijkstra朴素版精讲
47. 参加科学大会
思路
本题就是求最短路最短路是图论中的经典问题即给出一个有向图一个起点一个终点问起点到终点的最短路径。
接下来讲解最短路算法中的 dijkstra 算法。
dijkstra算法在有权图权值非负数中求从起点到其他节点的最短路径算法。
需要注意两点
dijkstra 算法可以同时求 起点到所有节点的最短路径权值不能为负数
dijkstra 算法 同样是贪心的思路不断寻找距离 源点最近的没有访问过的节点。
这里给出 dijkstra三部曲
第一步选源点到哪个节点近且该节点未被访问过第二步该最近节点被标记访问过第三步更新非访问节点到源点的距离即更新minDist数组
大家此时已经会发现这和prim算法 怎么这么像呢。
我在prim算法讲解中也给出了三部曲。 prim 和 dijkstra 确实很像思路也是类似的这一点我在后面还会详细来讲。
在dijkstra算法中同样有一个数组很重要起名为minDist。
minDist数组 用来记录 每一个节点距离源点的最小距离。
理解这一点很重要也是理解 dijkstra 算法的核心所在。
先来画图看一下 dijkstra 的工作过程以本题示例为例 以下为朴素版dijkstra的思路
示例中节点编号是从1开始所以为了让大家看的不晕minDist数组下标我也从 1 开始计数下标0 就不使用了这样 下标和节点标号就可以对应上了避免大家搞混 朴素版dijkstra
模拟过程
0、初始化
minDist数组数值初始化为int最大值。
这里在强点一下 minDist数组的含义记录所有节点到源点的最短路径那么初始化的时候就应该初始为最大值这样才能在后续出现最短路径的时候及时更新。 图中max 表示默认值节点0 不做处理统一从下标1 开始计算这样下标和节点数值统一 方便大家理解避免搞混
源点节点1 到自己的距离为0所以 minDist[1] 0
此时所有节点都没有被访问过所以 visited数组都为0 以下为dijkstra 三部曲
1、选源点到哪个节点近且该节点未被访问过
源点距离源点最近距离为0且未被访问。
2、该最近节点被标记访问过
标记源点访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图 更新 minDist数组即源点节点1 到 节点2 和 节点3的距离。
源点到节点2的最短距离为1小于原minDist[2]的数值max更新minDist[2] 1源点到节点3的最短距离为4小于原minDist[3]的数值max更新minDist[3] 4
遍历更新minDist的点是当前访问节点的邻接点。
1、选源点到哪个节点近且该节点未被访问过
未访问过的节点中源点到节点2距离最近选节点2
2、该最近节点被标记访问过
节点2被标记访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图 更新 minDist数组即源点节点1 到 节点6 、 节点3 和 节点4的距离。
为什么更新这些节点呢 怎么不更新其他节点呢
因为 源点节点1通过 已经计算过的节点节点2 可以链接到的节点 有 节点3节点4和节点6.
更新 minDist数组
源点到节点6的最短距离为5小于原minDist[6]的数值max更新minDist[6] 5源点到节点3的最短距离为3小于原minDist[3]的数值4更新minDist[3] 3源点到节点4的最短距离为6小于原minDist[4]的数值max更新minDist[4] 6
1、选源点到哪个节点近且该节点未被访问过
未访问过的节点中源点距离哪些节点最近怎么算的
其实就是看 minDist数组里的数值minDist 记录了 源点到所有节点的最近距离结合visited数组筛选出未访问的节点就好。
从 上面的图或者 从minDist数组中我们都能看出 未访问过的节点中源点节点1到节点3距离最近。
2、该最近节点被标记访问过
节点3被标记访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图 由于节点3的加入那么源点可以有新的路径链接到节点4 所以更新minDist数组
更新 minDist数组
源点到节点4的最短距离为5小于原minDist[4]的数值6更新minDist[4] 5 1、选源点到哪个节点近且该节点未被访问过
距离源点最近且没有被访问过的节点有节点4 和 节点6距离源点距离都是 5 minDist[4] 5minDist[6] 5 选哪个节点都可以。
2、该最近节点被标记访问过
节点4被标记访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图 由于节点4的加入那么源点可以链接到节点5 所以更新minDist数组
源点到节点5的最短距离为8小于原minDist[5]的数值max更新minDist[5] 8 1、选源点到哪个节点近且该节点未被访问过
距离源点最近且没有被访问过的节点是节点6距离源点距离是 5 minDist[6] 5
2、该最近节点被标记访问过
节点6 被标记访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图 由于节点6的加入那么源点可以链接到节点7 所以 更新minDist数组
源点到节点7的最短距离为14小于原minDist[7]的数值max更新minDist[7] 14 1、选源点到哪个节点近且该节点未被访问过
距离源点最近且没有被访问过的节点是节点5距离源点距离是 8 minDist[5] 8
2、该最近节点被标记访问过
节点5 被标记访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图 由于节点5的加入那么源点有新的路径可以链接到节点7 所以 更新minDist数组
源点到节点7的最短距离为12小于原minDist[7]的数值14更新minDist[7] 12 1、选源点到哪个节点近且该节点未被访问过
距离源点最近且没有被访问过的节点是节点7终点距离源点距离是 12 minDist[7] 12
2、该最近节点被标记访问过
节点7 被标记访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图 节点7加入但节点7到节点7的距离为0所以 不用更新minDist数组 最后我们要求起点节点1 到终点 节点7的距离。
再来回顾一下minDist数组的含义记录 每一个节点距离源点的最小距离。
那么起到节点1到终点节点7的最短距离就是 minDist[7] 按上面举例讲解来说minDist[7] 12节点1 到节点7的最短路径为 12。
路径如图 在上面的讲解中每一步 我都是按照 dijkstra 三部曲来讲解的理解了这三部曲代码也就好懂的。
代码如下
import java.util.*;
import java.util.List;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();int[][] grid new int[n1][n1];for(int[] array : grid){Arrays.fill(array,Integer.MAX_VALUE);}//读入图for(int i 0 ; i m ; i){int from scanner.nextInt();int to scanner.nextInt();int value scanner.nextInt();grid[from][to] value;}int[] minDist new int[n1];boolean[] visited new boolean[n1];int source 1;int destination n;visited[source] true;Arrays.fill(minDist,Integer.MAX_VALUE);minDist[source] 0;//dijkstra算法大循环遍历所有节点for(int i 0 ; i n ; i){int cur 1;int minValue Integer.MAX_VALUE;//找到当前非访问过的节点中最近的节点。for(int j 1 ; j n ; j){if(visited[j]) continue;if(minDist[j] minValue){minValue minDist[j];cur j;}}visited[cur] true;//针对该节点的邻接点 中的 非访问过的 节点 到 source的距离进行更新for(int j 1 ; j n ; j){if(!visited[j] grid[cur][j] ! Integer.MAX_VALUE minDist[cur] grid[cur][j] minDist[j]){minDist[j] minDist[cur] grid[cur][j];}}}if(minDist[destination] ! Integer.MAX_VALUE){System.out.println(minDist[destination]);}else{System.out.println(-1);}}}
如何求路径
如果要记录路径的话也是用一维parent数组来记录类似于prim算法在更新minDist的时候记录即可。
import java.util.*;
import java.util.List;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();int[][] grid new int[n1][n1];int[] parent new int[n1]; //用以记录路径Arrays.fill(parent,-1);for(int[] array : grid){Arrays.fill(array,Integer.MAX_VALUE);}//读入图for(int i 0 ; i m ; i){int from scanner.nextInt();int to scanner.nextInt();int value scanner.nextInt();grid[from][to] value;}int[] minDist new int[n1];boolean[] visited new boolean[n1];int source 1;int destination n;visited[source] true;Arrays.fill(minDist,Integer.MAX_VALUE);minDist[source] 0;//dijkstra算法大循环遍历所有节点for(int i 0 ; i n ; i){int cur 1;int minValue Integer.MAX_VALUE;//找到当前非访问过的节点中最近的节点。for(int j 1 ; j n ; j){if(visited[j]) continue;if(minDist[j] minValue){minValue minDist[j];cur j;}}visited[cur] true;//针对该节点的邻接点 中的 非访问过的 节点 到 source的距离进行更新for(int j 1 ; j n ; j){if(!visited[j] grid[cur][j] ! Integer.MAX_VALUE minDist[cur] grid[cur][j] minDist[j]){minDist[j] minDist[cur] grid[cur][j];parent[j] cur;//记录路径}}}if(minDist[destination] ! Integer.MAX_VALUE){System.out.println(minDist[destination]);}else{System.out.println(-1);}}}
debug方法
在每一次选择后输出日志输出当前选择的节点和minDist数组看和自己的预期是否相同。
出现负数
如果图中边的权值为负数dijkstra 还合适吗
看一下这个图 有负权值 节点1 到 节点5 的最短路径 应该是 节点1 - 节点2 - 节点3 - 节点4 - 节点5
那我们来看dijkstra 求解的路径是什么样的继续dijkstra 三部曲来模拟 dijkstra模拟过程上面已经详细讲过以下只模拟重要过程例如如何初始化就省略讲解了 初始化 1、选源点到哪个节点近且该节点未被访问过
源点距离源点最近距离为0且未被访问。
2、该最近节点被标记访问过
标记源点访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图 更新 minDist数组即源点节点1 到 节点2 和 节点3的距离。
源点到节点2的最短距离为100小于原minDist[2]的数值max更新minDist[2] 100源点到节点3的最短距离为1小于原minDist[3]的数值max更新minDist[4] 1 1、选源点到哪个节点近且该节点未被访问过
源点距离节点3最近距离为1且未被访问。
2、该最近节点被标记访问过
标记节点3访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图 由于节点3的加入那么源点可以有新的路径链接到节点4 所以更新minDist数组
源点到节点4的最短距离为2小于原minDist[4]的数值max更新minDist[4] 2 1、选源点到哪个节点近且该节点未被访问过
源点距离节点4最近距离为2且未被访问。
2、该最近节点被标记访问过
标记节点4访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图 由于节点4的加入那么源点可以有新的路径链接到节点5 所以更新minDist数组
源点到节点5的最短距离为3小于原minDist[5]的数值max更新minDist[5] 5 1、选源点到哪个节点近且该节点未被访问过
源点距离节点5最近距离为3且未被访问。
2、该最近节点被标记访问过
标记节点5访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图 节点5的加入而节点5 没有链接其他节点 所以不用更新minDist数组仅标记节点5被访问过了 1、选源点到哪个节点近且该节点未被访问过
源点距离节点2最近距离为100且未被访问。
2、该最近节点被标记访问过
标记节点2访问过
3、更新非访问节点到源点的距离即更新minDist数组 如图 至此dijkstra的模拟过程就结束了根据最后的minDist数组我们求 节点1 到 节点5 的最短路径的权值总和为 3路径 节点1 - 节点3 - 节点4 - 节点5
通过以上的过程模拟我们可以发现 之所以 没有走有负权值的最短路径 是因为 在 访问 节点 2 的时候节点 3 已经访问过了就不会再更新了。
那有录友可能会想 我可以改代码逻辑啊访问过的节点也让它继续访问不就好了
那么访问过的节点还能继续访问会不会有死循环的出现呢控制逻辑不让其死循环那特殊情况自己能都想清楚吗可以试试实践出真知
对于负权值的出现大家可以针对某一个场景 不断去修改 dijkstra 的代码但最终会发现只是 拆了东墙补西墙对dijkstra的补充逻辑只能满足某特定场景最短路求解。
对于求解带有负权值的最短路问题可以使用 Bellman-Ford 算法 后序会详细讲解。 dijkstra与prim算法的区别
大家可以发现 dijkstra的代码看上去 怎么和 prim算法这么像呢。
其实代码大体不差唯一区别在 三部曲中的 第三步 更新minDist数组
因为prim是求 非访问节点到最小生成树的最小距离而 dijkstra是求 非访问节点到源点的最小距离。
prim 更新 minDist数组的写法
for (int j 1; j v; j) {if (!isInTree[j] grid[cur][j] minDist[j]) {minDist[j] grid[cur][j];}
}
因为 minDist表示 节点到最小生成树的最小距离所以 新节点cur的加入只需要 使用 grid[cur][j] grid[cur][j] 就表示 cur 加入生成树后生成树到 节点j 的距离。
dijkstra 更新 minDist数组的写法
for (int v 1; v n; v) {if (!visited[v] grid[cur][v] ! INT_MAX minDist[cur] grid[cur][v] minDist[v]) {minDist[v] minDist[cur] grid[cur][v];}
}
因为 minDist表示 节点到源点的最小距离所以 新节点 cur 的加入需要使用 源点到cur的距离 minDist[cur] cur 到 节点 v 的距离 grid[cur][v]才是 源点到节点v的距离。
此时大家可能不禁要想 prim算法 可以有负权值吗
当然可以prim算法只需要将节点以最小权值和链接在一起不涉及到单一路径。 二、dijkstra堆优化版精讲
在节点数很大的情况下稀疏图考虑维护边集合来实现dijkstra算法。
使用邻接表来存储图。
同时因为每一步要选择未访问节点中minDist最小的节点考虑使用堆来进行优化。
堆优化细节
其实思路依然是 dijkstra 三部曲
第一步选源点到哪个节点近且该节点未被访问过第二步该最近节点被标记访问过第三步更新非访问节点到源点的距离即更新minDist数组
只不过之前是 通过遍历节点来遍历边通过两层for循环来寻找距离源点最近节点。 这次我们直接遍历边且通过堆来对边进行排序达到直接选择距离源点最近节点。
先来看一下针对这三部曲如果用 堆来优化。
那么三部曲中的第一步选源点到哪个节点近且该节点未被访问过我们如何选
我们要选择距离源点近的节点即该边的权值最小所以 我们需要一个 小顶堆 来帮我们对边的权值排序每次从小顶堆堆顶 取边就是权值最小的边。
C定义小顶堆可以用优先级队列实现代码如下
// 小顶堆
class mycomparison {
public:bool operator()(const pairint, int lhs, const pairint, int rhs) {return lhs.second rhs.second;}
};
// 优先队列中存放 pair节点编号源点到该节点的权值
priority_queuepairint, int, vectorpairint, int, mycomparison pq;
pairint, int中 第二个int 为什么要存 源点到该节点的权值因为 这个小顶堆需要按照权值来排序
有了小顶堆自动对边的权值排序那我们只需要直接从 堆里取堆顶元素小顶堆中最小的权值在上面就可以取到离源点最近的节点了 未访问过的节点不会加到堆里进行排序
所以三部曲中的第一步我们不用 for循环去遍历直接取堆顶元素
// pair节点编号源点到该节点的权值
pairint, int cur pq.top(); pq.pop();第二步该最近节点被标记访问过 这个就是将 节点做访问标记和 朴素dijkstra 一样 代码如下
// 2. 第二步该最近节点被标记访问过
visited[cur.first] true;cur.first 是指取 pairint, int 里的第一个int即节点编号
第三步更新非访问节点到源点的距离这里的思路 也是 和朴素dijkstra一样的。
但很多录友对这里是最懵的主要是因为两点
没有理解透彻 dijkstra 的思路没有理解 邻接表的表达方式
我们来回顾一下 朴素dijkstra 在这一步的代码和思路如果没看过我讲解的朴素版dijkstra这里会看不懂 // 3、第三步更新非访问节点到源点的距离即更新minDist数组
for (int v 1; v n; v) {if (!visited[v] grid[cur][v] ! INT_MAX minDist[cur] grid[cur][v] minDist[v]) {minDist[v] minDist[cur] grid[cur][v];}
}
其中 for循环是用来做什么的 是为了 找到 节点cur 链接指向了哪些节点因为使用邻接矩阵的表达方式 所以把所有节点遍历一遍。
而在邻接表中我们可以以相对高效的方式知道一个节点链接指向哪些节点。
再回顾一下邻接表的构造数组 链表 假如 加入的cur 是节点 2 那么 grid[2] 表示的就是图中第二行链表。 grid数组的构造我们在 上面 「图的存储」中讲过
所以在邻接表中我们要获取 节点cur 链接指向哪些节点就是遍历 grid[cur节点编号] 这个链表。
这个遍历方式C代码如下
for (Edge edge : grid[cur.first])
cur.first 就是cur节点编号 参考上面pair的定义 pair节点编号源点到该节点的权值
接下来就是更新 非访问节点到源点的距离代码实现和 朴素dijkstra 是一样的代码如下
// 3. 第三步更新非访问节点到源点的距离即更新minDist数组
for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点cur指向的节点为 edge// cur指向的节点edge.to这条边的权值为 edge.valif (!visited[edge.to] minDist[cur.first] edge.val minDist[edge.to]) { // 更新minDistminDist[edge.to] minDist[cur.first] edge.val;pq.push(pairint, int(edge.to, minDist[edge.to]));}
}
确定该节点没有被访问过!visited[edge.to] 目前 源点到cur.first的最短距离minDist cur.first 到 edge.to 的距离 edge.val 是否 小于 minDist已经记录的 源点到 edge.to 的距离 minDist[edge.to]
如果是的话就开始更新操作。
即
if (!visited[edge.to] minDist[cur.first] edge.val minDist[edge.to]) { // 更新minDistminDist[edge.to] minDist[cur.first] edge.val;pq.push(pairint, int(edge.to, minDist[edge.to])); // 由于cur节点的加入而新链接的边加入到优先级队里中
}
同时由于cur节点的加入源点又有可以新链接到的边将这些边加入到优先级队里中。
以上代码思路 和 朴素版dijkstra 是一样一样的主要区别是两点
邻接表的表示方式不同使用优先级队列小顶堆来对新链接的边排序
代码实现
堆优化dijkstra完整代码如下
#include iostream
#include vector
#include list
#include queue
#include climits
using namespace std;
// 小顶堆
class mycomparison {
public:bool operator()(const pairint, int lhs, const pairint, int rhs) {return lhs.second rhs.second;}
};
// 定义一个结构体来表示带权重的边
struct Edge {int to; // 邻接顶点int val; // 边的权重Edge(int t, int w): to(t), val(w) {} // 构造函数
};int main() {int n, m, p1, p2, val;cin n m;vectorlistEdge grid(n 1);for(int i 0; i m; i){cin p1 p2 val; // p1 指向 p2权值为 valgrid[p1].push_back(Edge(p2, val));}int start 1; // 起点int end n; // 终点// 存储从源点到每个节点的最短距离std::vectorint minDist(n 1, INT_MAX);// 记录顶点是否被访问过std::vectorbool visited(n 1, false); // 优先队列中存放 pair节点源点到该节点的权值priority_queuepairint, int, vectorpairint, int, mycomparison pq;// 初始化队列源点到源点的距离为0所以初始为0pq.push(pairint, int(start, 0)); minDist[start] 0; // 起始点到自身的距离为0while (!pq.empty()) {// 1. 第一步选源点到哪个节点近且该节点未被访问过 通过优先级队列来实现// 节点 源点到该节点的距离pairint, int cur pq.top(); pq.pop();if (visited[cur.first]) continue;// 2. 第二步该最近节点被标记访问过visited[cur.first] true;// 3. 第三步更新非访问节点到源点的距离即更新minDist数组for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点cur指向的节点为 edge// cur指向的节点edge.to这条边的权值为 edge.valif (!visited[edge.to] minDist[cur.first] edge.val minDist[edge.to]) { // 更新minDistminDist[edge.to] minDist[cur.first] edge.val;pq.push(pairint, int(edge.to, minDist[edge.to]));}}}if (minDist[end] INT_MAX) cout -1 endl; // 不能到达终点else cout minDist[end] endl; // 到达终点最短路径
}时间复杂度O(ElogE) E 为边的数量空间复杂度O(N E) N 为节点的数量
堆优化的时间复杂度 只和边的数量有关 和节点数无关在 优先级队列中 放的也是边。
以上代码中while (!pq.empty()) 里套了 for (Edge edge : grid[cur.first])
for 里 遍历的是 当前节点 cur 所连接边。
那 当前节点cur 所连接的边 也是不固定的 这就让大家分不清这时间复杂度究竟是多少
其实 for (Edge edge : grid[cur.first]) 里最终的数据走向 是 给队列里添加边。
那么跳出局部代码整个队列 一定是 所有边添加了一次同时也弹出了一次。
所以边添加一次时间复杂度是 O(E) while (!pq.empty()) 里每次都要弹出一个边来进行操作在优先级队列小顶堆中 弹出一个元素的时间复杂度是 O(logE) 这是堆排序的时间复杂度。
当然小顶堆里 是 添加元素的时候 排序还是 取数元素的时候排序这个无所谓时间复杂度都是O(E)总之是一定要排序的而小顶堆里也不会滞留元素有多少元素添加 一定就有多少元素弹出
所以 该算法整体时间复杂度为 OElogE)
网上的不少分析 会把 n 节点的数量算进来这个分析是有问题的举一个极端例子在n 为 10000且是有一条边的 图里以上代码大家感觉执行了多少次
while (!pq.empty()) 中的 pq 存的是边其实只执行了一次。
所以该算法时间复杂度 和 节点没有关系。
至于空间复杂度邻接表是 数组 链表 数组的空间 是 N 有E条边 就申请对应多少个链表节点所以是 复杂度是 N E
Java实现如下 import java.util.*;
import java.util.List;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();if(n 1){System.out.println(0);return ;}int m scanner.nextInt();//邻接表存储表ListListEdge grid new ArrayList(n1);for(int i 0 ; i n ; i){grid.add(new ArrayList());}//读入表for(int i 0 ; i m ; i){int from scanner.nextInt();int to scanner.nextInt();int value scanner.nextInt();grid.get(from).add(new Edge(to,value));}//构建优先队列维护边集合PriorityQueueEdge pq new PriorityQueue(new MyComparision());boolean[] visited new boolean[n1];int[] minDist new int[n1];Arrays.fill(minDist,Integer.MAX_VALUE);//初始化int start 1;int destination n;minDist[start] 0;pq.add(new Edge(start,0));//dijkstra算法while(!pq.isEmpty()){//访问距离源点最小的未访问过的节点Edge edge pq.poll();if(visited[edge.to]) continue;visited[edge.to] true;//更新当前访问节点的 未访问过的邻接点的 minDistfor(Edge e : grid.get(edge.to)){if(visited[e.to] false minDist[edge.to] e.value minDist[e.to]){minDist[e.to] minDist[edge.to] e.value;pq.add(new Edge(e.to,minDist[e.to]));//pq中加入更新过的节点及其对应的与源点的距离。//这里不用作删除操作因为取的一定是权重最小的那一个并且访问过之后由于visited数组存在不会再次访问}}}if(minDist[destination] Integer.MAX_VALUE){System.out.println(-1);}else{System.out.println(minDist[destination]);}}}class Edge{int to;int value;Edge(int to , int value){this.to to;this.value value;}}class MyComparision implements ComparatorEdge{Overridepublic int compare(Edge o1, Edge o2) {return Integer.compare(o1.value,o2.value);}
}
也可以像C里一样定义一个Pair类使用泛型PriorityQueue里维护Pair import java.util.*;class Edge {int to; // 邻接顶点int val; // 边的权重Edge(int to, int val) {this.to to;this.val val;}
}class MyComparison implements ComparatorPairInteger, Integer {Overridepublic int compare(PairInteger, Integer lhs, PairInteger, Integer rhs) {return Integer.compare(lhs.second, rhs.second);}
}class PairU, V {public final U first;public final V second;public Pair(U first, V second) {this.first first;this.second second;}
}public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();ListListEdge grid new ArrayList(n 1);for (int i 0; i n; i) {grid.add(new ArrayList());}for (int i 0; i m; i) {int p1 scanner.nextInt();int p2 scanner.nextInt();int val scanner.nextInt();grid.get(p1).add(new Edge(p2, val));}int start 1; // 起点int end n; // 终点// 存储从源点到每个节点的最短距离int[] minDist new int[n 1];Arrays.fill(minDist, Integer.MAX_VALUE);// 记录顶点是否被访问过boolean[] visited new boolean[n 1];// 优先队列中存放 Pair节点源点到该节点的权值PriorityQueuePairInteger, Integer pq new PriorityQueue(new MyComparison());// 初始化队列源点到源点的距离为0所以初始为0pq.add(new Pair(start, 0));minDist[start] 0; // 起始点到自身的距离为0while (!pq.isEmpty()) {// 1. 第一步选源点到哪个节点近且该节点未被访问过通过优先级队列来实现// 节点 源点到该节点的距离PairInteger, Integer cur pq.poll();if (visited[cur.first]) continue;// 2. 第二步该最近节点被标记访问过visited[cur.first] true;// 3. 第三步更新非访问节点到源点的距离即更新minDist数组for (Edge edge : grid.get(cur.first)) { // 遍历 cur指向的节点cur指向的节点为 edge// cur指向的节点edge.to这条边的权值为 edge.valif (!visited[edge.to] minDist[cur.first] edge.val minDist[edge.to]) { // 更新minDistminDist[edge.to] minDist[cur.first] edge.val;pq.add(new Pair(edge.to, minDist[edge.to]));}}}if (minDist[end] Integer.MAX_VALUE) {System.out.println(-1); // 不能到达终点} else {System.out.println(minDist[end]); // 到达终点最短路径}}
}
拓展
当然也有录友可能想 堆优化dijkstra 中 我为什么一定要用邻接表呢我就用邻接矩阵 行不行
也行的。
但 正是因为稀疏图所以我们使用堆优化的思路 如果我们还用 邻接矩阵 去表达这个图的话就是 一个高效的算法 使用了低效的数据结构那么 整体算法效率 依然是低的。
总结
在学习一种优化思路的时候首先就要知道为什么要优化遇到了什么问题。
正如我在开篇就给大家交代清楚 堆优化方式的背景。
堆优化的整体思路和 朴素版是大体一样的区别是 堆优化从边的角度出发且利用堆来排序。 三、Bellman_ford 算法精讲
本题依然是单源最短路问题求 从 节点1 到节点n 的最小费用。 但本题不同之处在于 边的权值是有负数了。
Bellman_ford算法可以解决图中有负权值的求单源最短路问题不能解决有负环的问题。
Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作n为节点数量从而求得目标最短路。 什么叫做松弛
《算法四》里面把这个操作叫做 “放松” 英文版里叫做 “relax the edge”
所以大家翻译过来就是 “放松” 或者 “松弛” 。
但《算法四》没有具体去讲这个 “放松” 究竟是个啥 网上很多题解也没有讲题解里的 “松弛这条边松弛所有边”等等 里面的 “松弛” 究竟是什么意思
这里我给大家举一个例子每条边有起点、终点和边的权值。例如一条边节点A 到 节点B 权值为value如图 minDist[B] 表示 到达B节点 最小权值minDist[B] 有哪些状态可以推出来
状态一 minDist[A] value 可以推出 minDist[B] 状态二 minDist[B]本身就有权值 可能是其他边链接的节点B 例如节点C以至于 minDist[B]记录了其他边到minDist[B]的权值
minDist[B] 应为如何取舍。
本题我们要求最小权值那么 这两个状态我们就取最小的
if (minDist[B] minDist[A] value) minDist[B] minDist[A] value
也就是说如果 通过 A 到 B 这条边可以获得更短的到达B节点的路径即如果 minDist[B] minDist[A] value那么我们就更新 minDist[B] minDist[A] value 这个过程就叫做 “松弛” 。
以上讲了这么多其实都是围绕以下这句代码展开
if (minDist[B] minDist[A] value) minDist[B] minDist[A] value
这句代码就是 Bellman_ford算法的核心操作。
以上代码也可以这么写minDist[B] min(minDist[A] value, minDist[B])
如果大家看过代码随想录的动态规划章节会发现 无论是背包问题还是子序列问题这段代码递推公式出现频率非常高的。
其实 Bellman_ford算法 也是采用了动态规划的思想即将一个问题分解成多个决策阶段通过状态之间的递归关系最后计算出全局最优解。
即 松弛操作就是Bellman_ford算法里进行动态规划中的一个单步操作这个单步操作取当前遍历到的元素 在 当前状态下 最优的minDist. 那么为什么是 n - 1次 松弛呢
这里要模拟一遍 Bellman_ford 的算法才行接下来看对所有边松弛 n - 1 次的操作是什么样的。
依然使用minDist数组来表达 起点到各个节点的最短距离例如minDist[3] 5 表示起点到达节点3 的最小距离为5
模拟过程
初始化过程。
起点为节点1 起点到起点的距离为0所以 minDist[1] 初始化为0
如图 其他节点对应的minDist初始化为max因为我们要求最小距离那么还没有计算过的节点 默认是一个最大数这样才能更新最小距离。
对所有边 进行第一次松弛 什么是松弛在上面我已经详细讲过
以示例给出的所有边为例
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5接下来我们来松弛一遍所有的边。
边节点5 - 节点6权值为-2 minDist[5] 还是默认数值max所以不能基于 节点5 去更新节点6如图 在复习一下minDist[5] 表示起点到节点5的最短距离
边节点1 - 节点2权值为1 minDist[2] minDist[1] 1 更新 minDist[2] minDist[1] 1 0 1 1 如图 边节点5 - 节点3权值为1 minDist[5] 还是默认数值max所以不能基于节点5去更新节点3 如图 边节点2 - 节点5权值为2 minDist[5] minDist[2] 2 经过上面的计算minDist[2]已经不是默认值而是 1更新 minDist[5] minDist[2] 2 1 2 3 如图 边节点2 - 节点4权值为-3 minDist[4] minDist[2] (-3)更新 minDist[4] minDist[2] (-3) 1 (-3) -2 如图 边节点4 - 节点6权值为4 minDist[6] minDist[4] 4更新 minDist[6] minDist[4] 4 -2 4 2 边节点1 - 节点3权值为5 minDist[3] minDist[1] 5更新 minDist[3] minDist[1] 5 0 5 5 如图 以上是对所有边进行一次松弛之后的结果。
那么需要对所有边松弛几次才能得到 起点节点1 到终点节点6的最短距离呢
对所有边松弛一次相当于计算 起点到达 与起点一条边相连的节点 的最短距离。
上面的距离中我们得到里 起点达到 与起点一条边相邻的节点2 和 节点3 的最短距离分别是 minDist[2] 和 minDist[3]
这里有录友疑惑了 minDist[3] 5分明不是 起点到达 节点3 的最短距离节点1 - 节点2 - 节点5 - 节点3 这条路线 距离才是4。
注意我上面讲的是 对所有边松弛一次相当于计算 起点到达 与起点一条边相连的节点 的最短距离这里 说的是 一条边相连的节点。
与起点节点1一条边相邻的节点到达节点2 最短距离是 1到达节点3 最短距离是5。
而 节点1 - 节点2 - 节点5 - 节点3 这条路线 是 与起点 三条边相连的路线了。
所以对所有边松弛一次 能得到 与起点 一条边相连的节点最短距离。
那对所有边松弛两次 可以得到与起点 两条边相连的节点的最短距离。
那对所有边松弛三次 可以得到与起点 三条边相连的节点的最短距离这个时候我们就能得到到达节点3真正的最短距离也就是 节点1 - 节点2 - 节点5 - 节点3 这条路线。
那么再回归刚刚的问题需要对所有边松弛几次才能得到 起点节点1 到终点节点6的最短距离呢
节点数量为n那么起点到终点最多是 n-1 条边相连。
那么无论图是什么样的边是什么样的顺序我们对所有边松弛 n-1 次 就一定能得到 起点到达 终点的最短距离。
其实也同时计算出了起点 到达 所有节点的最短距离因为所有节点与起点连接的边数最多也就是 n-1 条边。
截止到这里Bellman_ford 的核心算法思路大家就了解的差不多了。
共有两个关键点。
“松弛”究竟是个啥为什么要对所有边松弛 n - 1 次 n为节点个数
那么Bellman_ford的解题解题过程其实就是对所有边松弛 n-1 次然后得出得到终点的最短路径。
Java实现如下
import java.util.*;
import java.util.List;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();ListEdge edges new ArrayList();for(int i 0 ; i m ; i){edges.add(new Edge(scanner.nextInt(),scanner.nextInt(),scanner.nextInt()));}//初始化int start 1;int end n;int[] minDist new int[n1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[start] 0;for(int i 0 ; i n-1 ; i){//对所有的边进行n-1次松弛操作for(Edge edge : edges){if(minDist[edge.from] ! Integer.MAX_VALUE minDist[edge.from] edge.value minDist[edge.to]){minDist[edge.to] minDist[edge.from] edge.value;}}}if(minDist[end] Integer.MAX_VALUE){System.out.println(unconnected);}else{System.out.println(minDist[end]);}}}class Edge{int from;int to;int value;Edge(int from, int to , int value){this.from from;this.to to;this.value value;}}总结
Bellman_ford 是可以计算 负权值的单源最短路算法。
其算法核心思路是对 所有边进行 n-1 次 松弛。
弄清楚 什么是 松弛 为什么要 n-1 次 对理解Bellman_ford 非常重要。 四、Bellman_ford 队列优化算法又名SPFA
94. 城市间货物运输 I
可以发现 Bellman_ford 算法每次松弛 都是对所有边进行松弛。
但真正有效的松弛是基于已经计算过的节点在做的松弛。
给大家举一个例子 本图中对所有边进行松弛真正有效的松弛只有松弛 边节点1-节点2 和 边节点1-节点3 。
而松弛 边节点4-节点6 边节点5-节点3等等 都是无效的操作因为 节点4 和 节点 5 都是没有被计算过的节点。
所以 Bellman_ford 算法 每次都是对所有边进行松弛其实是多做了一些无用功。
只需要对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛就够了。对上一轮更新结点的出发边做松弛
基于以上思路如何记录 上次松弛的时候更新过的节点呢
用队列来记录。其实用栈也行对元素顺序没有要求 模拟过程
接下来来举例这个队列是如何工作的。
以示例给出的所有边为例
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5我们依然使用minDist数组来表达 起点到各个节点的最短距离例如minDist[3] 5 表示起点到达节点3 的最小距离为5
初始化起点为节点1 起点到起点的最短距离为0所以minDist[1] 为 0。 将节点1 加入队列 下次松弛从节点1开始 从队列里取出节点1松弛节点1 作为出发点连接的边节点1 - 节点2和边节点1 - 节点3
边节点1 - 节点2权值为1 minDist[2] minDist[1] 1 更新 minDist[2] minDist[1] 1 0 1 1 。
边节点1 - 节点3权值为5 minDist[3] minDist[1] 5更新 minDist[3] minDist[1] 5 0 5 5。
将节点2、节点3 加入队列如图 从队列里取出节点2松弛节点2 作为出发点连接的边节点2 - 节点4和边节点2 - 节点5
边节点2 - 节点4权值为1 minDist[4] minDist[2] (-3) 更新 minDist[4] minDist[2] (-3) 1 (-3) -2 。
边节点2 - 节点5权值为2 minDist[5] minDist[2] 2 更新 minDist[5] minDist[2] 2 1 2 3 。
将节点4节点5 加入队列如图 从队列里出去节点3松弛节点3 作为出发点连接的边。
因为没有从节点3作为出发点的边所以这里就从队列里取出节点3就好不用做其他操作如图 从队列中取出节点4松弛节点4作为出发点连接的边节点4 - 节点6
边节点4 - 节点6权值为4 minDist[6] minDist[4] 4更新 minDist[6] minDist[4] 4 -2 4 2 。
将节点6加入队列
如图 从队列中取出节点5松弛节点5作为出发点连接的边节点5 - 节点3边节点5 - 节点6
边节点5 - 节点3权值为1 minDist[3] minDist[5] 1 更新 minDist[3] minDist[5] 1 3 1 4
边节点5 - 节点6权值为-2 minDist[6] minDist[5] (-2) 更新 minDist[6] minDist[5] (-2) 3 - 2 1
如图将节点3加入队列因为节点6已经在队列里所以不用重复添加 所以我们在加入队列的过程可以有一个优化用visited数组记录已经在队列里的元素已经在队列的元素不用重复加入 从队列中取出节点6松弛节点6 作为出发点连接的边。
节点6作为终点没有可以出发的边。
同理从队列中取出节点3也没有可以出发的边
所以直接从队列中取出如图 这样我们就完成了基于队列优化的bellman_ford的算法模拟过程。
大家可以发现 基于队列优化的算法要比bellman_ford 算法 减少很多无用的松弛情况特别是对于边数众多的大图 优化效果明显。
Java代码如下
import java.util.*;
import java.util.List;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();ListListEdge edges new ArrayList(n1);for(int i 0 ; i n; i){edges.add(new ArrayList());}for(int i 0 ; i m ; i){int from scanner.nextInt();int to scanner.nextInt();int value scanner.nextInt();edges.get(from).add(new Edge(from,to,value));}boolean[] visited new boolean[n1];int[] minDist new int[n1];Arrays.fill(minDist,Integer.MAX_VALUE);int start 1;int end n;minDist[start] 0;QueueInteger queue new ArrayDeque();queue.add(start);visited[start] true;//进行松弛操作while(!queue.isEmpty()){int node queue.remove();visited[node] false;for(Edge edge : edges.get(node)){if(!visited[node] minDist[node] edge.value minDist[edge.to]){minDist[edge.to] minDist[node] edge.value;queue.add(edge.to);visited[edge.to] true;}}}if(minDist[end] Integer.MAX_VALUE){System.out.println(unconnected);}else{System.out.println(minDist[end]);}}}class Edge{int from;int to;int value;Edge(int from, int to , int value){this.from from;this.to to;this.value value;}}
效率分析
队列优化版Bellman_ford 的时间复杂度 并不稳定效率高低依赖于图的结构。
例如 如果是一个双向图且每一个节点和所有其他节点都相连的话那么该算法的时间复杂度就接近于 Bellman_ford 的 O(N * E) N 为节点数量E为边的数量。
在这种图中每一个节点都会重复加入队列 n - 1次因为 这种图中 每个节点 都有 n-1 条指向该节点的边每条边指向该节点就需要加入一次队列。
如果图越稠密则 SPFA的效率越接近与 Bellman_ford。
反之图越稀疏SPFA的效率就越高。
一般来说SPFA 的时间复杂度为 O(K * N) K 为不定值因为 节点需要计入几次队列取决于 图的稠密度。
如果图是一条线形图且单向的话每个节点的入度为1那么只需要加入一次队列这样时间复杂度就是 O(N)。
所以 SPFA 在最坏的情况下是 O(N * E)但 一般情况下 时间复杂度为 O(K * N)。
尽管如此以上分析都是 理论上的时间复杂度分析。
并没有计算 出队列 和 入队列的时间消耗。 因为这个在不同语言上 时间消耗也是不一定的。
拓展
这里可能有录友疑惑while (!que.empty()) 队里里 会不会造成死循环 例如 图中有环这样一直有元素加入到队列里
其实有环的情况要看它是 正权回路 还是 负权回路。
题目描述中已经说了本题没有 负权回路 。
如图 正权回路 就是有环但环的总权值为正数。
在有环且只有正权回路的情况下即使元素重复加入队列最后也会因为 所有边都松弛后节点数值minDist数组不在发生变化了 而终止。
而且有重复元素加入队列是正常的多条路径到达同一个节点节点必要要选择一个最短的路径而这个节点就会重复加入队列进行判断选一个最短的
在0094.城市间货物运输I 中我们讲过对所有边 最多松弛 n -1 次就一定可以求出所有起点到所有节点的最小距离即 minDist数组。
即使再松弛n次以上 所有起点到所有节点的最小距离minDist数组 不会再变了。 这里如果不理解建议认真看0094.城市间货物运输I讲解
所以本题我们使用队列优化有元素重复加入队列也会因为最后 minDist数组 不会在发生变化而终止。
节点再加入队列需要有松弛的行为 而 每个节点已经都计算出来 起点到该节点的最短路径那么就不会有 执行这个判断条件if (minDist[to] minDist[from] value)从而不会有新的节点加入到队列。
但如果本题有 负权回路那情况就不一样了。 五、bellman_ford之判断负权回路
95. 城市间货物运输 II
本题中在评估从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本时存在一种情况图中可能出现负权回路。
负权回路是指一系列道路的总权值为负这样的回路使得通过反复经过回路中的道路理论上可以无限地减少总成本或无限地增加总收益。
为了避免货物运输商采用负权回路这种情况无限的赚取政府补贴算法还需检测这种特殊情况。
思路
使用 bellman_ford 算法来判断 负权回路。
在 kama94.城市间货物运输I 中 我们讲了 bellman_ford 算法的核心就是一句话对 所有边 进行 n-1 次松弛。 同时文中的 【拓展】部分 我们也讲了 松弛n次以上 会怎么样
在没有负权回路的图中松弛 n 次以上 结果不会有变化。
但本题有 负权回路如果松弛 n 次结果就会有变化了因为 有负权回路 就是可以无限最短路径一直绕圈就可以一直得到无限小的最短距离。
那么每松弛一次都会更新最短路径所以结果会一直有变化。
在代码中进行n次松弛前n-1次计算最短路第n次判断是否有负环。如果第n次仍然有minDist需要更新的情况那么说明有负环
import java.util.*;
import java.util.List;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();ListEdge edges new ArrayList();for(int i 0 ; i m ; i){edges.add(new Edge(scanner.nextInt(),scanner.nextInt(),scanner.nextInt()));}//初始化int start 1;int end n;int[] minDist new int[n1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[start] 0;boolean flag false;for(int i 0 ; i n ; i){//对所有的边进行n次松弛操作其中第n次用于判断是否有负环if(i n-1){for(Edge edge : edges){if(minDist[edge.from] ! Integer.MAX_VALUE minDist[edge.from] edge.value minDist[edge.to]){minDist[edge.to] minDist[edge.from] edge.value;}}}else{for(Edge edge : edges){if(minDist[edge.from] ! Integer.MAX_VALUE minDist[edge.from] edge.value minDist[edge.to]){flag true;break;}}}}if(flag){System.out.println(circle);}else if(minDist[end] Integer.MAX_VALUE){System.out.println(unconnected);}else{System.out.println(minDist[end]);}}}class Edge{int from;int to;int value;Edge(int from, int to , int value){this.from from;this.to to;this.value value;}}
拓展
本题可不可 使用 队列优化版的bellman_fordSPFA呢
上面的解法中我们对所有边松弛了n-1次后在松弛一次如果出现minDist出现变化就判断有负权回路。
如果使用 SPFA 那么节点都是进队列的那么节点进入队列几次后 足够判断该图是否有负权回路呢
在 0094.城市间货物运输I-SPFA 中我们讲过 在极端情况下即所有节点都与其他节点相连每个节点的入度为 n-1 n为节点数量所以每个节点最多加入 n-1 次队列。
那么如果节点加入队列的次数 超过了 n-1次 那么该图就一定有负权回路。
所以本题也是可以使用 SPFA 来做的。 六、bellman_ford之单源有限最短路
96. 城市间货物运输 III
本题要求计算在最多经过 k 个城市的条件下从城市 src 到城市 dst 的最低运输成本。
根据bellman_ford算法的思路容易想到可以进行k1次松弛。
问题在于在每一次松弛的时候受到松弛边的处理顺序的影响当前在处理的边的结果可能在本次松弛过程中影响到其他边实际起到了一条边被多次松弛的效果这就导致了k实际上不起作用这不是我们期望的。
我们期望的是第一次松弛只更新和start直接相连的边第二次松弛在第一次松弛的基础上更新和start间隔1个城市的边。参考讲解代码随想录bellman_ford之单源有限最短路
那么只需要将上一次的minDist记录下来本次更新使用上一次的minDist避免本次更新minDist过程中使用到本次的结果。
Java实现如下
import java.util.*;
import java.util.List;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();ListEdge edges new ArrayList();for(int i 0; i m; i){int from scanner.nextInt();int to scanner.nextInt();int value scanner.nextInt();edges.add(new Edge(from,to,value));}int[] minDist new int[n1];int[] minDist_pre ;Arrays.fill(minDist,Integer.MAX_VALUE);int start scanner.nextInt();int end scanner.nextInt();minDist[start] 0;int k scanner.nextInt();for(int i 0 ; i k1 ; i){minDist_pre Arrays.copyOf(minDist,n1);for(Edge edge : edges){if(minDist_pre[edge.from] ! Integer.MAX_VALUE minDist_pre[edge.from] edge.value minDist[edge.to]){//要更新的是 minDist[edge.to] 使用 minDist_pre进行更新minDist[edge.to] minDist_pre[edge.from] edge.value;}}}if(minDist[end] Integer.MAX_VALUE){System.out.println(unreachable);}else{System.out.println(minDist[end]);}}}class Edge{int from;int to;int value;Edge(int from, int to , int value){this.from from;this.to to;this.value value;}}拓展一边的顺序的影响
其实边的顺序会影响我们每一次拓展的结果。
我来给大家举个例子。
我上面讲解中给出的示例是这样的
4 4
1 2 -1
2 3 1
3 1 -1
3 4 1
1 4 3我将示例中边的顺序改一下给成
4 4
3 1 -1
3 4 1
2 3 1
1 2 -1
1 4 3所构成是图是一样的都是如下的这个图但给出的边的顺序是不一样的。 再用版本一的代码是运行一下发现结果输出是 1 是对的。 分明刚刚输出的结果是 -2是错误的怎么 一样的图这次输出的结果就对了呢
其实这是和示例中给出的边的顺序是有关的
我们按照修改后的示例再来模拟 对所有边的第一次拓展情况。
初始化 边节点3 - 节点1权值为-1 节点3还没有被计算过节点1 不更新。
边节点3 - 节点4权值为1 节点3还没有被计算过节点4 不更新。
边节点2 - 节点3权值为 1 节点2还没有被计算过节点3 不更新。
边节点1 - 节点2权值为 -1 minDist[2] minDist[1] (-1)更新 minDist[2] 0 (-1) -1 如图 以上是对所有边 松弛一次的状态。
可以发现 同样的图边的顺序不一样使用版本一的代码 每次松弛更新的节点也是不一样的。
而边的顺序是随机的是题目给我们的所以本题我们才需要 记录上一次松弛的minDist来保障 每一次对所有边松弛的结果。 拓展二本题本质
那么前面讲解过的 94.城市间货物运输I 和 95.城市间货物运输II 也是bellman_ford经典算法也没使用 minDist_copy怎么就没问题呢
94.城市间货物运输I 是没有 负权回路的那么 多松弛多少次对结果都没有影响。
求 节点1 到 节点n 的最短路径松弛n-1 次就够了松弛 大于 n-1次结果也不会变。
那么在对所有边进行第一次松弛的时候如果基于 本次计算的 minDist 来计算 minDist 相当于多做松弛了也是对最终结果没影响。
95.城市间货物运输II 是判断是否有 负权回路一旦有负权回路 对所有边松弛 n-1 次以后在做松弛 minDist 数值一定会变根据这一点来判断是否有负权回路。
所以95.城市间货物运输II 只需要判断minDist数值变化了就行而 minDist 的数值对不对并不是我们关心的。
那么本题 为什么计算minDist 一定要基于上次 的 minDist 数值。
其关键在于本题的两个因素
本题可以有负权回路说明只要多做松弛结果是会变的。本题要求最多经过k个节点对松弛次数是有限制的。这就不允许有多松弛的效果
如果本题中 没有负权回路的测试用例 那版本一的代码就可以过了也就不用我费这么大口舌去讲解的这个坑了。 拓展三SPFA
本题也可以用 SPFA来做关于 SPFA 已经在这里 0094.城市间货物运输I-SPFA 有详细讲解。
使用SPFA算法解决本题的时候关键在于 如何控制松弛k次。
其实实现不难但有点技巧可以用一个变量 que_size 记录每一轮松弛入队列的所有节点数量。
下一轮松弛的时候就把队列里 que_size 个节点都弹出来就是上一轮松弛入队列的节点。
SPFA实际上更符合对k个节点的要求更加直观
代码如下详细注释
#include iostream
#include vector
#include queue
#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 n, m, p1, p2, val;cin n m;vectorlistEdge grid(n 1); // 邻接表// 将所有边保存起来for(int i 0; i m; i){cin p1 p2 val;// p1 指向 p2权值为 valgrid[p1].push_back(Edge(p2, val));}int start, end, k;cin start end k;k;vectorint minDist(n 1 , INT_MAX);vectorint minDist_copy(n 1); // 用来记录每一次遍历的结果minDist[start] 0;queueint que;que.push(start); // 队列里放入起点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);}}}}if (minDist[end] INT_MAX) cout unreachable endl;else cout minDist[end] endl;}
时间复杂度 O(K * H) H 为不确定数取决于 图的稠密度但H 一定是小于等于 E 的
关于 SPFA的是时间复杂度分析我在0094.城市间货物运输I-SPFA 有详细讲解
但大家会发现以上代码大家提交后怎么耗时这么多 理论上SPFA的时间复杂度不是要比 bellman_ford 更优吗
怎么耗时多了这么多呢
以上代码有一个可以改进的点每一轮松弛中重复节点可以不用入队列。
因为重复节点入队列下次从队列里取节点的时候该节点要取很多次而且都是重复计算。
所以代码可以优化成这样
#include iostream
#include vector
#include queue
#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 n, m, p1, p2, val;cin n m;vectorlistEdge grid(n 1); // 邻接表// 将所有边保存起来for(int i 0; i m; i){cin p1 p2 val;// p1 指向 p2权值为 valgrid[p1].push_back(Edge(p2, val));}int start, end, k;cin start end k;k;vectorint minDist(n 1 , INT_MAX);vectorint minDist_copy(n 1); // 用来记录每一次遍历的结果minDist[start] 0;queueint que;que.push(start); // 队列里放入起点int que_size;while (k-- !que.empty()) {vectorbool visited(n 1, false); // 每一轮松弛中控制节点不用重复入队列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;if(visited[to]) continue; // 不用重复放入队列但需要重复松弛所以放在这里位置visited[to] true;que.push(to);}}}}if (minDist[end] INT_MAX) cout unreachable endl;else cout minDist[end] endl;
}
以上代码提交后耗时情况 大家发现 依然远比 bellman_ford 的代码版本 耗时高。
这又是为什么呢
对于后台数据我特别制作的一个稠密大图该图有250个节点和10000条边 在这种情况下 SPFA 的时间复杂度 是接近与 bellman_ford的。
但因为 SPFA 节点的进出队列操作耗时很大所以相同的时间复杂度的情况下SPFA 实际上更耗时了。
这一点我在 0094.城市间货物运输I-SPFA 有分析感兴趣的录友再回头去看看。 拓展四能否用dijkstra
本题能否使用 dijkstra 算法呢
dijkstra 是贪心的思路 每一次搜索都只会找距离源点最近的非访问过的节点。
如果限制最多访问k个节点那么 dijkstra 未必能在有限次就能到达终点即使在经过k个节点确实可以到达终点的情况下。
这么说大家会感觉有点抽象我用 dijkstra朴素版精讲 里的示例在举例说明 如果没看过我讲的dijkstra朴素版精讲建议去仔细看一下否则下面讲解容易看不懂
在以下这个图中求节点1 到 节点7 最多经过2个节点 的最短路是多少呢 最短路显然是 最多经过2个节点也就是3条边相连的路线节点1 - 节点2 - 节点6- 节点7
如果是 dijkstra 求解的话求解过程是这样的 下面是dijkstra的模拟过程我精简了很多如果看不懂一定要先看dijkstra朴素版精讲
初始化如图所示 找距离源点最近且没有被访问过的节点先找节点1 距离源点最近且没有被访问过的节点找节点2 距离源点最近且没有被访问过的节点找到节点3 距离源点最近且没有被访问过的节点找到节点4 此时最多经过2个节点的搜索就完毕了但结果中minDist[7] 即节点7的结果并没有被更。
那么 dijkstra 会告诉我们 节点1 到 节点7 最多经过2个节点的情况下是不可到达的。
通过以上模拟过程大家应该能感受到 dijkstra 贪心的过程正是因为 贪心所以 dijkstra 找不到 节点1 - 节点2 - 节点6- 节点7 这条路径。
本质上的原因是dijkstra是贪心的。
总结
本题是单源有限最短路问题也是 bellman_ford的一个拓展问题如果理解bellman_ford 其实思路比较容易理解但有很多细节。
例如 为什么要用 minDist_copy 来记录上一轮 松弛的结果。 这也是本篇我为什么花了这么大篇幅讲解的关键所在。
接下来还给大家做了四个拓展
边的顺序的影响本题的本质SPFA的解法能否用dijkstra
学透了以上四个拓展相信大家会对bellman_ford有更深入的理解。 七、Floyd 算法精讲
97. 小明逛公园
思路
本题是经典的多源最短路问题即 求多个起点到多个终点的多条最短路径。
通过本题来系统讲解一个新的最短路算法-Floyd 算法。
Floyd 算法对边的权值正负没有要求都可以处理。
Floyd算法核心思想是动态规划。
例如我们再求节点1 到 节点9 的最短距离用二维数组来表示即grid[1][9]如果最短距离是10 那就是 grid[1][9] 10。
那 节点1 到 节点9 的最短距离 是不是可以由 节点1 到节点5的最短距离 节点5到节点9的最短距离组成呢
即 grid[1][9] grid[1][5] grid[5][9]
节点1 到节点5的最短距离 是不是可以有 节点1 到 节点3的最短距离 节点3 到 节点5 的最短距离组成呢
即 grid[1][5] grid[1][3] grid[3][5]
以此类推节点1 到 节点3的最短距离 可以由更小的区间组成。
那么这样我们是不是就找到了子问题推导求出整体最优方案的递归关系呢。
节点1 到 节点9 的最短距离 可以由 节点1 到节点5的最短距离 节点5到节点9的最短距离组成 也可以有 节点1 到节点7的最短距离 节点7 到节点9的最短距离的距离组成。
那么选哪个呢
是不是 要选一个最小的毕竟是求最短路。
此时我们已经接近明确递归公式了。
之前在讲解动态规划的时候给出过动规五部曲
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
那么接下来我们还是用这五部来给大家讲解 Floyd。
1、dp数组及下标含义
grid[i][j][k] m表示 从节点 i 考虑经过可以选择经过或者不经过节点1~k 到节点j 的代价是m.
2、确定递推公式
想要从 grid[i][j][k-1] 得到 grid[i][j][k] 考虑两种情况
1从i到j的最短路径经过节点k那么
grid[i][j][k] grid[i][k][k-1] grid[k][j][k-1] 右边的两个依赖项均计算过了
2从i到j的最短路径经过节点k那么
grid[i][j][k] grid[i][j][k-1]
综上递推公式为 grid[i][j][k] Math.min(grid[i][k][k-1] grid[k][j][k-1] , grid[i][j][k-1]);
3、初始化
考虑 k 0 的情况 根据定义此时grid[i][j][0] 是 从i到j不经过任何节点所要付出的代价那么只能是i和j直接相连所以在读入边的时候对grid[i][j][0]和 grid[j][i][0]初始化成对应的权重无向图
4、遍历顺序
dp数组是三维数组初始化的都是k0这个平面要保证每一次计算的时候它所以来的项都已经计算出来并且依赖于之前计算的结果这就要求从k0这个平面一层一层向上计算。所以最外层的循环是k内层的i的循环和j的循环可以交换。
5、dp模拟
日志输出的时候可以按k0,1,2...逐层输出。
Java实现如下
import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();int[][][] grid new int[n1][n1][n1];for(int[][] grid1 : grid){for(int[] grid2 : grid1){Arrays.fill(grid2,Integer.MAX_VALUE);}}//读图初始化for(int i 0 ; i m; i){int start scanner.nextInt();int end scanner.nextInt();int value scanner.nextInt();grid[start][end][0] value;grid[end][start][0] value;}//动态规划for(int k 1 ; k n ; k){for(int i 1 ; i n; i){for(int j 1 ; j n; j){if(grid[i][k][k-1] Integer.MAX_VALUE || grid[k][j][k-1] Integer.MAX_VALUE) grid[i][j][k] grid[i][j][k-1];else grid[i][j][k] Math.min(grid[i][k][k-1] grid[k][j][k-1],grid[i][j][k-1]); //如果初始化成Integer.MAX_VALUE,这里可能溢出可以先判断一下是不是}}}//答案输出int plans scanner.nextInt();for(int i 0 ; i plans ; i){int start scanner.nextInt();int end scanner.nextInt();if(grid[start][end][n] ! Integer.MAX_VALUE){System.out.println(grid[start][end][n]);}else{System.out.println(-1);}}}}注意一个问题dp数组递推的过程中可能会出现Integer.MAX_VALUE相加导致溢出需要预先判断一下。
也可以选择一个题目中一定不会到达的大数同时还能够避免溢出的 来初始化。 空间优化
这里 我们可以做一下 空间上的优化从滚动数组的角度来看我们定义一个 grid[n 1][ n 1][2] 这么大的数组就可以因为k 只是依赖于 k-1的状态并不需要记录k-2k-3k-4 等等这些状态。
那么我们只需要记录 grid[i][j][1] 和 grid[i][j][0] 就好之后就是 grid[i][j][1] 和 grid[i][j][0] 交替滚动。
在进一步想如果本层计算本层计算即k相同从三维角度来讲 grid[i][j] 用到了 本层中刚计算好的 grid[i][k] 会有什么问题吗
如果 本层刚计算好的 grid[i][k] 比上一层 即k-1层计算的 grid[i][k] 小说明确实有 i 到 k 的更短路径那么基于 更小的 grid[i][k] 去计算 gird[i][j] 没有问题。
如果 本层刚计算好的 grid[i][k] 比上一层 即k-1层计算的 grid[i][k] 大 这不可能因为这样也不会做更新 grid[i][k]的操作。
所以本层计算中使用了本层计算过的 grid[i][k] 和 grid[k][j] 是没问题的。
那么就没必要区分grid[i][k] 和 grid[k][j] 是 属于 k - 1 层的呢还是 k 层的。
所以递归公式可以为
grid[i][j] min(grid[i][j], grid[i][k] grid[k][j]);
Java实现如下
import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();int[][] grid new int[n1][n1];for(int[] grid1 : grid){Arrays.fill(grid1,Integer.MAX_VALUE);}//读图初始化for(int i 0 ; i m; i){int start scanner.nextInt();int end scanner.nextInt();int value scanner.nextInt();grid[start][end] value;grid[end][start] value;}//动态规划for(int k 1; k n ; k){for(int i 1; i n ; i){for(int j 1 ; j n ; j){if(grid[i][k] Integer.MAX_VALUE || grid[k][j] Integer.MAX_VALUE) continue;else grid[i][j] Math.min(grid[i][j],grid[i][k] grid[k][j]);}}}//答案输出int plans scanner.nextInt();for(int i 0 ; i plans ; i){int start scanner.nextInt();int end scanner.nextInt();if(grid[start][end] ! Integer.MAX_VALUE){System.out.println(grid[start][end]);}else{System.out.println(-1);}}}}
总结
本期如果上来只用二维数组来讲的话其实更容易但遍历顺序那里用二维数组其实是讲不清楚的所以我直接用三维数组来讲目的是将遍历顺序这里讲清楚。
理解了遍历顺序才是floyd算法最精髓的地方。
floyd算法的时间复杂度相对较高适合 稠密图且源点较多的情况。
如果是稀疏图floyd是从节点的角度去计算了例如 图中节点数量是 1000就一条边那 floyd的时间复杂度依然是 O(n^3) 。
如果 源点少其实可以 多次dijsktra 求源点到终点。 八、A * 算法精讲 A star算法
127. 骑士的攻击
bfs
本题要求求最短路径容易想到bfs
Java实现
import java.util.*;public class Main {static int[][]directions {{1,2},{2,1},{-1,2},{2,-1},{1,-2},{-2,1},{-1,-2},{-2,-1}};public static void main(String[] args) {int[][] grid new int[1001][1001];Scanner scanner new Scanner(System.in);int n scanner.nextInt();for(int i 0 ; i n; i){//注意每次都要把grid清0for(int[] l : grid){Arrays.fill(l,0);}int startX scanner.nextInt();int startY scanner.nextInt();int endX scanner.nextInt();int endY scanner.nextInt();if(startX endX startY endY){System.out.println(0);continue;}Queueint[] queue new ArrayDeque();queue.add(new int[]{startX,startY});while(!queue.isEmpty()){int[] nowLocation queue.remove();int nowX nowLocation[0];int nowY nowLocation[1];for(int j 0 ; j 8 ; j){int nextX nowX directions[j][0];int nextY nowY directions[j][1];if(nextX 1 || nextX 1000 || nextY 1 || nextY 1000) continue;if(grid[nextX][nextY] 0){grid[nextX][nextY] grid[nowX][nowY] 1;queue.add(new int[]{nextX,nextY});}}if(grid[endX][endY] ! 0) break;}System.out.println(grid[endX][endY]);}}}
C实现
#includeiostream
#includequeue
#includestring.h
using namespace std;
int moves[1001][1001];
int dir[8][2]{-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
void bfs(int a1,int a2, int b1, int b2)
{queueint q;q.push(a1);q.push(a2);while(!q.empty()){int mq.front(); q.pop();int nq.front(); q.pop();if(m b1 n b2)break;for(int i0;i8;i){int mmm dir[i][0];int nnn dir[i][1];if(mm 1 || mm 1000 || nn 1 || nn 1000)continue;if(!moves[mm][nn]){moves[mm][nn]moves[m][n]1;q.push(mm);q.push(nn);}}}
}int main()
{int n, a1, a2, b1, b2;cin n;while (n--) {cin a1 a2 b1 b2;memset(moves,0,sizeof(moves));bfs(a1, a2, b1, b2);cout moves[b1][b2] endl;}return 0;
}
但提交后会时间超限。
Astar
Astar 是一种 广搜的改良版。 有的是 Astar是 dijkstra 的改良版。
其实只是场景不同而已 我们在搜索最短路的时候 如果是无权图边的权值都是1 那就用广搜代码简洁时间效率和 dijkstra 差不多 具体要取决于图的稠密
如果是有权图边有不同的权值优先考虑 dijkstra。
而 Astar 关键在于 启发式函数 也就是 影响 广搜或者 dijkstra 从 容器队列里取元素的优先顺序。
A*算法通过启发函数的设计实现有方向地搜索。
那么启发式函数落实到代码处如果指引搜索的方向
在本篇开篇中给出了BFS代码指引 搜索的方向的关键代码在这里
int mq.front();q.pop();
int nq.front();q.pop();
从队列里取出什么元素接下来就是从哪里开始搜索。
所以 启发式函数 要影响的就是队列里元素的排序
这是影响BFS搜索方向的关键。
对队列里节点进行排序就需要给每一个节点权值如何计算权值呢
每个节点的权值为F给出公式为F G H
G起点达到目前遍历节点的距离
F目前遍历的节点到达终点的距离
起点达到目前遍历节点的距离 目前遍历的节点到达终点的距离 就是起点到达终点的距离。
本题的图是无权网格状在计算两点距离通常有如下三种计算方式
曼哈顿距离计算方式 d abs(x1-x2)abs(y1-y2)欧氏距离欧拉距离 计算方式d sqrt( (x1-x2)^2 (y1-y2)^2 )切比雪夫距离计算方式d max(abs(x1 - x2), abs(y1 - y2))
x1, x2 为起点坐标y1, y2 为终点坐标 abs 为求绝对值sqrt 为求开根号
选择哪一种距离计算方式 也会导致 A * 算法的结果不同。
本题采用欧拉距离才能最大程度体现 点与点之间的距离。
所以 使用欧拉距离计算 和 广搜搜出来的最短路的节点数是一样的。 路径可能不同但路径上的节点数是相同的
可以使用 优先级队列 帮我们排好序每次出队列就是F最小的节点。 Java实现
import java.util.*;class Knight{int x;int y;int g;int h;int weight;Knight(int x, int y){this.x x;this.y y;}void calWeight(int g,int endX,int endY){this.g g;this.h (x - endX) * (x - endX) (y - endY) * (y - endY); // 统一不开根号这样可以提高精度this.weight this.g this.h;}
}class MyComparison implements ComparatorKnight{Overridepublic int compare(Knight o1, Knight o2) {return Integer.compare(o1.weight,o2.weight);}
}public class Main {static int[][]directions {{1,2},{2,1},{-1,2},{2,-1},{1,-2},{-2,1},{-1,-2},{-2,-1}};static int endX;static int endY;static PriorityQueueKnight queue new PriorityQueue(new MyComparison());static int[][] grid new int[1001][1001];public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();for(int i 0 ; i n; i){for(int[] arr : grid){Arrays.fill(arr,0);}Knight knight new Knight(scanner.nextInt(),scanner.nextInt());endX scanner.nextInt();endY scanner.nextInt();knight.calWeight(0,endX,endY);astar(knight);while(!queue.isEmpty()) queue.remove();System.out.println(grid[endX][endY]);}}public static void astar(Knight knight){Knight cur,next;queue.add(knight);while(!queue.isEmpty()){cur queue.remove();if(cur.x endX cur.y endY) break;for(int i 0 ; i 8 ; i){int nextX cur.x directions[i][0];int nextY cur.y directions[i][1];if(nextX 1 || nextX 1000 || nextY 1 || nextY 1000) continue;if(grid[nextX][nextY] 0){grid[nextX][nextY] grid[cur.x][cur.y] 1;next new Knight(nextX,nextY);next.calWeight(cur.g5,endX,endY);//统一不开根号提高精度queue.add(next);}}}}}
感觉这里有必要讲解一下代码架构。
1为了实现对位置的排序定义了一个类Knight专门用来存储当前的位置、当前的g、h和weight。
2为了实现优先队列排序自定义了MyComparison 取 implements ComparatorKnight 实现对Knight的排序使用Integer.compare维护一个最小堆。
3Knight类中calWeight函数需要传入当前的gendX和endY用来计算h并把g和h加和得到weight。Knight的x,y是要在创建的时候传入的。
4将一些必要的量诸如gridendX,endY设为全局静态变量方便类内函数沟通降低传参的要求。但也要注意每一轮grid初始化每一轮要把queue清空。 C实现
#includeiostream
#includequeue
#includestring.h
using namespace std;
int moves[1001][1001];
int dir[8][2]{-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
int b1, b2;
// F G H
// G 从起点到该节点路径消耗
// H 该节点到终点的预估消耗struct Knight{int x,y;int g,h,f;bool operator (const Knight k) const{ // 重载运算符 从小到大排序return k.f f;}
};priority_queueKnight que;int Heuristic(const Knight k) { // 欧拉距离return (k.x - b1) * (k.x - b1) (k.y - b2) * (k.y - b2); // 统一不开根号这样可以提高精度
}
void astar(const Knight k)
{Knight cur, next;que.push(k);while(!que.empty()){curque.top(); que.pop();if(cur.x b1 cur.y b2)break;for(int i 0; i 8; i){next.x cur.x dir[i][0];next.y cur.y dir[i][1];if(next.x 1 || next.x 1000 || next.y 1 || next.y 1000)continue;if(!moves[next.x][next.y]){moves[next.x][next.y] moves[cur.x][cur.y] 1;// 开始计算Fnext.g cur.g 5; // 统一不开根号这样可以提高精度马走日1 * 1 2 * 2 5next.h Heuristic(next);next.f next.g next.h;que.push(next);}}}
}int main()
{int n, a1, a2;cin n;while (n--) {cin a1 a2 b1 b2;memset(moves,0,sizeof(moves));Knight start;start.x a1;start.y a2;start.g 0;start.h Heuristic(start);start.f start.g start.h;astar(start);while(!que.empty()) que.pop(); // 队列清空cout moves[b1][b2] endl;}return 0;
}
复杂度分析
A * 算法的时间复杂度 其实是不好去量化的因为他取决于 启发式函数怎么写。
最坏情况下A * 退化成广搜算法的时间复杂度 是 O(n * 2)n 为节点数量。
最佳情况是从起点直接到终点时间复杂度为 O(dlogd)d 为起点到终点的深度。
因为在搜索的过程中也需要堆排序所以是 O(dlogd)。
实际上 A * 的时间复杂度是介于 最优 和最坏 情况之间 可以 非常粗略的认为 A * 算法的时间复杂度是 O(nlogn) n 为节点数量。
A * 算法的空间复杂度 O(b ^ d) ,d 为起点到终点的深度b 是 图中节点间的连接数量本题因为是无权网格图所以 节点间连接数量为 4。
拓展
如果本题大家使用 曼哈顿距离 或者 切比雪夫距离 计算的话可以提交试一试有的最短路结果是并不是最短的。
原因也是 曼哈顿 和 切比雪夫这两种计算方式在 本题的网格地图中都没有体现出点到点的真正距离
可能有些录友找到类似的题目例如 poj 2243 (opens new window)使用 曼哈顿距离 提交也过了 那是因为题目中的地图太小了仅仅是一张 8 * 8的地图根本看不出来 不同启发式函数写法的区别。
A * 算法 并不是一个明确的最短路算法A * 算法搜的路径如何完全取决于 启发式函数怎么写。
A * 算法并不能保证一定是最短路因为在设计 启发式函数的时候要考虑 时间效率与准确度之间的一个权衡。
虽然本题中A * 算法得到是最短路也是因为本题 启发式函数 和 地图结构都是最简单的。
例如在游戏中在地图很大、不同路径权值不同、有障碍 且多个游戏单位在地图中寻路的情况如果要计算准确最短路耗时很大会给玩家一种卡顿的感觉。
而真实玩家在玩游戏的时候并不要求一定是最短路次短路也是可以的 玩家不一定能感受出来即使感受出来也不是很在意只要奔着目标走过去 大体就可以接受。
所以 在游戏开发设计中保证运行效率的情况下A * 算法中的启发式函数 设计往往不是最短路而是接近最短路的 次短路设计。 A * 的缺点
大家看上述 A * 代码的时候可以看到 我们想 队列里添加了很多节点但真正从队列里取出来的 仅仅是 靠启发式函数判断 距离终点最近的节点。
相对了 普通BFSA * 算法只从 队列里取出 距离终点最近的节点。
那么问题来了A * 在一次路径搜索中大量不需要访问的节点都在队列里会造成空间的过度消耗。
IDA * 算法 对这一空间增长问题进行了优化关于 IDA * 算法本篇不再做讲解感兴趣的录友可以自行找资料学习。
另外还有一种场景 是 A * 解决不了的。
如果题目中给出 多个可能的目标然后在这多个目标中 选择最近的目标这种 A * 就不擅长了 A * 只擅长给出明确的目标 然后找到最短路径。
如果是多个目标找最近目标特别是潜在目标数量很多的时候可以考虑 Dijkstra BFS 或者 Floyd。 总结参考最短路算法总结篇
图论总结参考图论总结篇
文章转载自： http://www.morning.wcft.cn.gov.cn.wcft.cn http://www.morning.fwllb.cn.gov.cn.fwllb.cn http://www.morning.bbgr.cn.gov.cn.bbgr.cn http://www.morning.bpmdn.cn.gov.cn.bpmdn.cn http://www.morning.lmcrc.cn.gov.cn.lmcrc.cn http://www.morning.ftync.cn.gov.cn.ftync.cn http://www.morning.mntxalcb.com.gov.cn.mntxalcb.com http://www.morning.rfzbm.cn.gov.cn.rfzbm.cn http://www.morning.nggry.cn.gov.cn.nggry.cn http://www.morning.hjbrd.cn.gov.cn.hjbrd.cn http://www.morning.wsrcy.cn.gov.cn.wsrcy.cn http://www.morning.rqknq.cn.gov.cn.rqknq.cn http://www.morning.lmfmd.cn.gov.cn.lmfmd.cn http://www.morning.hsjfs.cn.gov.cn.hsjfs.cn http://www.morning.pxtgf.cn.gov.cn.pxtgf.cn http://www.morning.wsgyq.cn.gov.cn.wsgyq.cn http://www.morning.rqkck.cn.gov.cn.rqkck.cn http://www.morning.knngw.cn.gov.cn.knngw.cn http://www.morning.nkmw.cn.gov.cn.nkmw.cn http://www.morning.ndltr.cn.gov.cn.ndltr.cn http://www.morning.kwqqs.cn.gov.cn.kwqqs.cn http://www.morning.qsy39.cn.gov.cn.qsy39.cn http://www.morning.clbzy.cn.gov.cn.clbzy.cn http://www.morning.mdjzydr.com.gov.cn.mdjzydr.com http://www.morning.wfbnp.cn.gov.cn.wfbnp.cn http://www.morning.jfymz.cn.gov.cn.jfymz.cn http://www.morning.kpwcx.cn.gov.cn.kpwcx.cn http://www.morning.fppzc.cn.gov.cn.fppzc.cn http://www.morning.pylpd.cn.gov.cn.pylpd.cn http://www.morning.muniubangcaishui.cn.gov.cn.muniubangcaishui.cn http://www.morning.yhywr.cn.gov.cn.yhywr.cn http://www.morning.yrhpg.cn.gov.cn.yrhpg.cn http://www.morning.ytmx.cn.gov.cn.ytmx.cn http://www.morning.bzqnp.cn.gov.cn.bzqnp.cn http://www.morning.hrdx.cn.gov.cn.hrdx.cn http://www.morning.lbrwm.cn.gov.cn.lbrwm.cn http://www.morning.fmrwl.cn.gov.cn.fmrwl.cn http://www.morning.tnyanzou.com.gov.cn.tnyanzou.com http://www.morning.gjwkl.cn.gov.cn.gjwkl.cn http://www.morning.hnzrl.cn.gov.cn.hnzrl.cn http://www.morning.yjfmj.cn.gov.cn.yjfmj.cn http://www.morning.yxbrn.cn.gov.cn.yxbrn.cn http://www.morning.fbylq.cn.gov.cn.fbylq.cn http://www.morning.jytrb.cn.gov.cn.jytrb.cn http://www.morning.rbbzn.cn.gov.cn.rbbzn.cn http://www.morning.mwbqk.cn.gov.cn.mwbqk.cn http://www.morning.dnpft.cn.gov.cn.dnpft.cn http://www.morning.zlzpz.cn.gov.cn.zlzpz.cn http://www.morning.ndyrb.com.gov.cn.ndyrb.com http://www.morning.mmqhq.cn.gov.cn.mmqhq.cn http://www.morning.lmdfj.cn.gov.cn.lmdfj.cn http://www.morning.liyixun.com.gov.cn.liyixun.com http://www.morning.hlrtzcj.cn.gov.cn.hlrtzcj.cn http://www.morning.1000sh.com.gov.cn.1000sh.com http://www.morning.ylkkh.cn.gov.cn.ylkkh.cn http://www.morning.qrlsy.cn.gov.cn.qrlsy.cn http://www.morning.nmkbl.cn.gov.cn.nmkbl.cn http://www.morning.nxstj.cn.gov.cn.nxstj.cn http://www.morning.rpzth.cn.gov.cn.rpzth.cn http://www.morning.pcqdf.cn.gov.cn.pcqdf.cn http://www.morning.zfqdt.cn.gov.cn.zfqdt.cn http://www.morning.nqmkr.cn.gov.cn.nqmkr.cn http://www.morning.kndyz.cn.gov.cn.kndyz.cn http://www.morning.klcdt.cn.gov.cn.klcdt.cn http://www.morning.mkbc.cn.gov.cn.mkbc.cn http://www.morning.wjyyg.cn.gov.cn.wjyyg.cn http://www.morning.ckbmz.cn.gov.cn.ckbmz.cn http://www.morning.bfmrq.cn.gov.cn.bfmrq.cn http://www.morning.twdwy.cn.gov.cn.twdwy.cn http://www.morning.ssrjt.cn.gov.cn.ssrjt.cn http://www.morning.rmppf.cn.gov.cn.rmppf.cn http://www.morning.qsy37.cn.gov.cn.qsy37.cn http://www.morning.sgrdp.cn.gov.cn.sgrdp.cn http://www.morning.nqwkn.cn.gov.cn.nqwkn.cn http://www.morning.dwrjj.cn.gov.cn.dwrjj.cn http://www.morning.mbfkt.cn.gov.cn.mbfkt.cn http://www.morning.fqljq.cn.gov.cn.fqljq.cn http://www.morning.frllr.cn.gov.cn.frllr.cn http://www.morning.qflwp.cn.gov.cn.qflwp.cn http://www.morning.qgdsd.cn.gov.cn.qgdsd.cn
