d…一、dijkstra朴素版精讲

本题就是求最短路最短路是图论中的经典问题即给出一个有向图一个起点一个终点问起点到终点的最短路径。

dijkstra

dijkstra算法在有权图权值非负数中求从起点到其他节点的最短路径算法。

需要注意两点

第一步选源点到哪个节点近且该节点未被访问过第二步该最近节点被标记访问过第三步更新非访问节点到源点的距离即更新minDist数组

大家此时已经会发现这和prim算法

在dijkstra算法中同样有一个数组很重要起名为minDist。

minDist数组

示例中节点编号是从1开始所以为了让大家看的不晕minDist数组下标我也从

开始计数下标0

minDist数组的含义记录所有节点到源点的最短路径那么初始化的时候就应该初始为最大值这样才能在后续出现最短路径的时候及时更新。

图中max

源点到节点2的最短距离为1小于原minDist[2]的数值max更新minDist[2]

1源点到节点3的最短距离为4小于原minDist[3]的数值max更新minDist[3]

minDist数组即源点节点1

源点到节点6的最短距离为5小于原minDist[6]的数值max更新minDist[6]

5源点到节点3的最短距离为3小于原minDist[3]的数值4更新minDist[3]

3源点到节点4的最短距离为6小于原minDist[4]的数值max更新minDist[4]

源点到所有节点的最近距离结合visited数组筛选出未访问的节点就好。

从minDist数组中我们都能看出

源点到节点4的最短距离为5小于原minDist[4]的数值6更新minDist[4]

minDist[4]

源点到节点5的最短距离为8小于原minDist[5]的数值max更新minDist[5]

minDist[6]

源点到节点7的最短距离为14小于原minDist[7]的数值max更新minDist[7]

minDist[5]

源点到节点7的最短距离为12小于原minDist[7]的数值14更新minDist[7]

minDist[7]

grid){Arrays.fill(array,Integer.MAX_VALUE);}//读入图for(int

i){int

scanner.nextInt();grid[from][to]

value;}int[]

true;Arrays.fill(minDist,Integer.MAX_VALUE);minDist[source]

i){int

Integer.MAX_VALUE;//找到当前非访问过的节点中最近的节点。

for(int

j){if(visited[j])

grid[cur][j];}}}if(minDist[destination]

Integer.MAX_VALUE){System.out.println(minDist[destination]);}else{System.out.println(-1);}}}

如何求路径

如果要记录路径的话也是用一维parent数组来记录类似于prim算法在更新minDist的时候记录即可。

import

//用以记录路径Arrays.fill(parent,-1);for(int[]

array

grid){Arrays.fill(array,Integer.MAX_VALUE);}//读入图for(int

i){int

scanner.nextInt();grid[from][to]

value;}int[]

true;Arrays.fill(minDist,Integer.MAX_VALUE);minDist[source]

i){int

Integer.MAX_VALUE;//找到当前非访问过的节点中最近的节点。

for(int

j){if(visited[j])

cur;//记录路径}}}if(minDist[destination]

Integer.MAX_VALUE){System.out.println(minDist[destination]);}else{System.out.println(-1);}}}

debug方法

在每一次选择后输出日志输出当前选择的节点和minDist数组看和自己的预期是否相同。

出现负数

dijkstra模拟过程上面已经详细讲过以下只模拟重要过程例如如何初始化就省略讲解了

初始化

源点到节点2的最短距离为100小于原minDist[2]的数值max更新minDist[2]

100源点到节点3的最短距离为1小于原minDist[3]的数值max更新minDist[4]

源点到节点4的最短距离为2小于原minDist[4]的数值max更新minDist[4]

源点到节点5的最短距离为3小于原minDist[5]的数值max更新minDist[5]

没有链接其他节点

至此dijkstra的模拟过程就结束了根据最后的minDist数组我们求

节点1

那么访问过的节点还能继续访问会不会有死循环的出现呢控制逻辑不让其死循环那特殊情况自己能都想清楚吗可以试试实践出真知

不断去修改

拆了东墙补西墙对dijkstra的补充逻辑只能满足某特定场景最短路求解。

Bellman-Ford

当然可以prim算法只需要将节点以最小权值和链接在一起不涉及到单一路径。

二、dijkstra堆优化版精讲

在节点数很大的情况下稀疏图考虑维护边集合来实现dijkstra算法。

同时因为每一步要选择未访问节点中minDist最小的节点考虑使用堆来进行优化。

堆优化细节

第一步选源点到哪个节点近且该节点未被访问过第二步该最近节点被标记访问过第三步更新非访问节点到源点的距离即更新minDist数组

通过遍历节点来遍历边通过两层for循环来寻找距离源点最近节点。

这次我们直接遍历边且通过堆来对边进行排序达到直接选择距离源点最近节点。

先来看一下针对这三部曲如果用

那么三部曲中的第一步选源点到哪个节点近且该节点未被访问过我们如何选

我们需要一个

堆里取堆顶元素小顶堆中最小的权值在上面就可以取到离源点最近的节点了

for循环去遍历直接取堆顶元素

在这一步的代码和思路如果没看过我讲解的朴素版dijkstra这里会看不懂

for

而在邻接表中我们可以以相对高效的方式知道一个节点链接指向哪些节点。

grid[2]

同时由于cur节点的加入源点又有可以新链接到的边将这些边加入到优先级队里中。

朴素版dijkstra

pair节点源点到该节点的权值priority_queuepairint,

int,

初始化队列源点到源点的距离为0所以初始为0pq.push(pairint,

int(start,

第二步该最近节点被标记访问过visited[cur.first]

true;//

第三步更新非访问节点到源点的距离即更新minDist数组for

(Edge

取数元素的时候排序这个无所谓时间复杂度都是O(E)总之是一定要排序的而小顶堆里也不会滞留元素有多少元素添加

一定就有多少元素弹出

1){System.out.println(0);return

;}int

scanner.nextInt();//邻接表存储表ListListEdge

grid

scanner.nextInt();grid.get(from).add(new

Edge(to,value));}//构建优先队列维护边集合PriorityQueueEdge

new

int[n1];Arrays.fill(minDist,Integer.MAX_VALUE);//初始化int

start

Edge(start,0));//dijkstra算法while(!pq.isEmpty()){//访问距离源点最小的未访问过的节点Edge

edge

grid.get(edge.to)){if(visited[e.to]

false

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

Integer.compare(o1.value,o2.value);}

也可以像C里一样定义一个Pair类使用泛型PriorityQueue里维护Pair

import

scanner.nextInt();grid.get(p1).add(new

Edge(p2,

Pair节点源点到该节点的权值PriorityQueuePairInteger,

Integer

初始化队列源点到源点的距离为0所以初始为0pq.add(new

Pair(start,

第一步选源点到哪个节点近且该节点未被访问过通过优先级队列来实现//

Integer

第二步该最近节点被标记访问过visited[cur.first]

true;//

第三步更新非访问节点到源点的距离即更新minDist数组for

(Edge

{System.out.println(minDist[end]);

到达终点最短路径}}

在学习一种优化思路的时候首先就要知道为什么要优化遇到了什么问题。

正如我在开篇就给大家交代清楚

Bellman_ford算法可以解决图中有负权值的求单源最短路问题不能解决有负环的问题。

什么叫做松弛

这里我给大家举一个例子每条边有起点、终点和边的权值。

例如一条边节点A

节点B

无论是背包问题还是子序列问题这段代码递推公式出现频率非常高的。

Bellman_ford算法

也是采用了动态规划的思想即将一个问题分解成多个决策阶段通过状态之间的递归关系最后计算出全局最优解。

松弛操作就是Bellman_ford算法里进行动态规划中的一个单步操作这个单步操作取当前遍历到的元素

当前状态下

其他节点对应的minDist初始化为max因为我们要求最小距离那么还没有计算过的节点

对所有边

三条边相连的节点的最短距离这个时候我们就能得到到达节点3真正的最短距离也就是

节点1

那么Bellman_ford的解题解题过程其实就是对所有边松弛

n-1

Edge(scanner.nextInt(),scanner.nextInt(),scanner.nextInt()));}//初始化int

start

int[n1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[start]

0;for(int

minDist[edge.to]){minDist[edge.to]

minDist[edge.from]

Integer.MAX_VALUE){System.out.println(unconnected);}else{System.out.println(minDist[end]);}}}class

Edge{int

因为没有从节点3作为出发点的边所以这里就从队列里取出节点3就好不用做其他操作如图

节点6

所以我们在加入队列的过程可以有一个优化用visited数组记录已经在队列里的元素已经在队列的元素不用重复加入

从队列中取出节点6松弛节点6

这样我们就完成了基于队列优化的bellman_ford的算法模拟过程。

Java代码如下

scanner.nextInt();edges.get(from).add(new

Edge(from,to,value));}boolean[]

visited

int[n1];Arrays.fill(minDist,Integer.MAX_VALUE);int

start

ArrayDeque();queue.add(start);visited[start]

true;//进行松弛操作while(!queue.isEmpty()){int

node

edges.get(node)){if(!visited[node]

minDist[node]

minDist[edge.to]){minDist[edge.to]

minDist[node]

edge.value;queue.add(edge.to);visited[edge.to]

Integer.MAX_VALUE){System.out.println(unconnected);}else{System.out.println(minDist[end]);}}}class

Edge{int

如果是一个双向图且每一个节点和所有其他节点都相连的话那么该算法的时间复杂度就接近于

Bellman_ford

如果图是一条线形图且单向的话每个节点的入度为1那么只需要加入一次队列这样时间复杂度就是

SPFA

而且有重复元素加入队列是正常的多条路径到达同一个节点节点必要要选择一个最短的路径而这个节点就会重复加入队列进行判断选一个最短的

在0094.城市间货物运输I

的所有可能路径中综合政府补贴后的最低运输成本时存在一种情况图中可能出现负权回路。

负权回路是指一系列道路的总权值为负这样的回路使得通过反复经过回路中的道路理论上可以无限地减少总成本或无限地增加总收益。

为了避免货物运输商采用负权回路这种情况无限的赚取政府补贴算法还需检测这种特殊情况。

bellman_ford

在代码中进行n次松弛前n-1次计算最短路第n次判断是否有负环。

如果第n次仍然有minDist需要更新的情况那么说明有负环

import

Edge(scanner.nextInt(),scanner.nextInt(),scanner.nextInt()));}//初始化int

start

int[n1];Arrays.fill(minDist,Integer.MAX_VALUE);minDist[start]

0;boolean

i){//对所有的边进行n次松弛操作其中第n次用于判断是否有负环if(i

n-1){for(Edge

minDist[edge.to]){minDist[edge.to]

minDist[edge.from]

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

上面的解法中我们对所有边松弛了n-1次后在松弛一次如果出现minDist出现变化就判断有负权回路。

如果使用

根据bellman_ford算法的思路容易想到可以进行k1次松弛。

问题在于在每一次松弛的时候受到松弛边的处理顺序的影响当前在处理的边的结果可能在本次松弛过程中影响到其他边实际起到了一条边被多次松弛的效果这就导致了k实际上不起作用这不是我们期望的。

我们期望的是第一次松弛只更新和start直接相连的边第二次松弛在第一次松弛的基础上更新和start间隔1个城市的边。

参考讲解代码随想录bellman_ford之单源有限最短路

那么只需要将上一次的minDist记录下来本次更新使用上一次的minDist避免本次更新minDist过程中使用到本次的结果。

Java实现如下

scanner.nextInt();edges.add(new

minDist

;Arrays.fill(minDist,Integer.MAX_VALUE);int

start

scanner.nextInt();minDist[start]

0;int

Arrays.copyOf(minDist,n1);for(Edge

edge

edges){if(minDist_pre[edge.from]

Integer.MAX_VALUE

minDist_pre进行更新minDist[edge.to]

Integer.MAX_VALUE){System.out.println(unreachable);}else{System.out.println(minDist[end]);}}}class

Edge{int

3所构成是图是一样的都是如下的这个图但给出的边的顺序是不一样的。

初始化

本题可以有负权回路说明只要多做松弛结果是会变的。

本题要求最多经过k个节点对松弛次数是有限制的。

这就不允许有多松弛的效果

如果本题中

那版本一的代码就可以过了也就不用我费这么大口舌去讲解的这个坑了。

拓展三SPFA

SPFA的是时间复杂度分析我在0094.城市间货物运输I-SPFA

有详细讲解

以上代码有一个可以改进的点每一轮松弛中重复节点可以不用入队列。

因为重复节点入队列下次从队列里取节点的时候该节点要取很多次而且都是重复计算。

#include

不用重复放入队列但需要重复松弛所以放在这里位置visited[to]

(minDist[end]

对于后台数据我特别制作的一个稠密大图该图有250个节点和10000条边

在这种情况下

节点的进出队列操作耗时很大所以相同的时间复杂度的情况下SPFA

这一点我在

未必能在有限次就能到达终点即使在经过k个节点确实可以到达终点的情况下。

这么说大家会感觉有点抽象我用

如果没看过我讲的dijkstra朴素版精讲建议去仔细看一下否则下面讲解容易看不懂

节点7

下面是dijkstra的模拟过程我精简了很多如果看不懂一定要先看dijkstra朴素版精讲

初始化如图所示

此时最多经过2个节点的搜索就完毕了但结果中minDist[7]

dijkstra

bellman_ford的一个拓展问题如果理解bellman_ford

为什么要用

学透了以上四个拓展相信大家会对bellman_ford有更深入的理解。

七、Floyd

的最短距离用二维数组来表示即grid[1][9]如果最短距离是10

grid[1][9]

那么这样我们是不是就找到了子问题推导求出整体最优方案的递归关系呢。

节点1

table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组

1、dp数组及下标含义

从i到j不经过任何节点所要付出的代价那么只能是i和j直接相连所以在读入边的时候对grid[i][j][0]和

4、遍历顺序

dp数组是三维数组初始化的都是k0这个平面要保证每一次计算的时候它所以来的项都已经计算出来并且依赖于之前计算的结果这就要求从k0这个平面一层一层向上计算。

所以最外层的循环是k内层的i的循环和j的循环可以交换。

5、dp模拟

grid1){Arrays.fill(grid2,Integer.MAX_VALUE);}}//读图初始化for(int

i){int

scanner.nextInt();grid[start][end][0]

value;}//动态规划for(int

grid[k][j][k-1],grid[i][j][k-1]);

//如果初始化成Integer.MAX_VALUE,这里可能溢出可以先判断一下是不是}}}//答案输出int

plans

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){Arrays.fill(grid1,Integer.MAX_VALUE);}//读图初始化for(int

i){int

scanner.nextInt();grid[start][end]

value;}//动态规划for(int

scanner.nextInt();if(grid[start][end]

Integer.MAX_VALUE){System.out.println(grid[start][end]);}else{System.out.println(-1);}}}}

本期如果上来只用二维数组来讲的话其实更容易但遍历顺序那里用二维数组其实是讲不清楚的所以我直接用三维数组来讲目的是将遍历顺序这里讲清楚。

1000就一条边那

{{1,2},{2,1},{-1,2},{2,-1},{1,-2},{-2,1},{-1,-2},{-2,-1}};public

static

endY){System.out.println(0);continue;}Queueint[]

queue

int[]{startX,startY});while(!queue.isEmpty()){int[]

nowLocation

int[]{nextX,nextY});}}if(grid[endX][endY]

break;}System.out.println(grid[endX][endY]);}}}

C实现

dir[8][2]{-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};

void

q;q.push(a1);q.push(a2);while(!q.empty()){int

mq.front();

1000)continue;if(!moves[mm][nn]){moves[mm][nn]moves[m][n]1;q.push(mm);q.push(nn);}}}

}int

b2;memset(moves,0,sizeof(moves));bfs(a1,

a2,

ComparatorKnight{Overridepublic

int

Integer.compare(o1.weight,o2.weight);}

}public

{{1,2},{2,1},{-1,2},{2,-1},{1,-2},{-2,1},{-1,-2},{-2,-1}};static

int

grid){Arrays.fill(arr,0);}Knight

knight

Knight(scanner.nextInt(),scanner.nextInt());endX

scanner.nextInt();knight.calWeight(0,endX,endY);astar(knight);while(!queue.isEmpty())

queue.remove();System.out.println(grid[endX][endY]);}}public

static

cur,next;queue.add(knight);while(!queue.isEmpty()){cur

endX

Knight(nextX,nextY);next.calWeight(cur.g5,endX,endY);//统一不开根号提高精度queue.add(next);}}}}}

1为了实现对位置的排序定义了一个类Knight专门用来存储当前的位置、当前的g、h和weight。

implements

实现对Knight的排序使用Integer.compare维护一个最小堆。

3Knight类中calWeight函数需要传入当前的gendX和endY用来计算h并把g和h加和得到weight。

Knight的x,y是要在创建的时候传入的。

4将一些必要的量诸如gridendX,endY设为全局静态变量方便类内函数沟通降低传参的要求。

但也要注意每一轮grid初始化每一轮要把queue清空。

C实现

dir[8][2]{-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};

int

next;que.push(k);while(!que.empty()){curque.top();

que.pop();if(cur.x

1000)continue;if(!moves[next.x][next.y]){moves[next.x][next.y]

moves[cur.x][cur.y]

b2;memset(moves,0,sizeof(moves));Knight

start;start.x

start.h;astar(start);while(!que.empty())

que.pop();

且多个游戏单位在地图中寻路的情况如果要计算准确最短路耗时很大会给玩家一种卡顿的感觉。

玩家不一定能感受出来即使感受出来也不是很在意只要奔着目标走过去

大家看上述

在一次路径搜索中大量不需要访问的节点都在队列里会造成空间的过度消耗。

IDA