图论 之 迪斯科特拉算法求解最短路径

求解最短路径的问题，分为使用BFS和使用迪斯科特拉算法，这两种算法求解的范围是有区别的

• BFS适合求解，边的权值都是1的图中的最短路径的问题
  图论 之 BFS
• 迪斯科特拉算法适合求解边的权值不一样的图，其中，该算法有两种实现方式，分别适用于两种情况的图
  • 稠密图，使用朴素的Dijkstra算法，其中稠密图的定义是，边的数量级与 $o(n^2)$相当的图，朴素的Dijkstra算法的时间复杂度是$o(n^2)$,其中n是图的节点的数量
  • 稀疏图，使用堆优化的Dijkstra算法，算法的时间复杂度是$o(mlogm)$其中，m是边的数量，如果输入的稠密图，那么使用堆优化的Dijkstra算法的时间复杂度是$o(n^{2}logn)$

---

朴素的Dijkstras算法的模版

# 存储边的情况
edge = [[float('inf')]*n for n in range(n)]
# dis[i]表示 单源点k到其余节点i的最短的路径
dis = [float('inf')]*n 
dis[k] = 0
# 这个done[k] = True不用设置，后面会依据这个，把起点弹出
done = [False]*n # done[i]标记是否找到 到达节点i的最短的路径while True:x = -1for i,ok in enumerate(done):# 找到在还没确定最小距离的节点，该节点到源点的距离最小if not ok and (x < 0 or dis[i] < dis[x]):x = i# 判断是否都找到了if x < 0:# 这里就已经求解完成了，后续你可以返回最大值？return dis# 有节点无法到达if dis[x] == float('inf'):return -1# 设置标志位，表示节点x的最小距离已经确定done[x] = True# 遍历当前节点的所有的邻居，更新答案for j,d in enumerate(edge[x]):dis[j] = min(dis[j],dis[j]+d)

使用堆优化的Dijkstra算法

import heapqclass Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:# 使用堆优化的Dijkstra算法# 使用堆优化的话，适用于稀疏图，所以边的记录，我们使用邻接表edge = [[] for _ in range(n)]for x,y,z in times:edge[x-1].append((y-1,z))dis = [float('inf')]*n dis[k-1] = 0# 入堆的元素是 (dis[x],x)，第一个元素是距离，这也是设置的优先级h = [(0,k-1)]while h:# 出堆dx,x = heapq.heappop(h)# 如果当前的距离大于最小距离，直接过if dx > dis[x]:# 说明之前出过堆continue# 访问邻居，不一定是这个邻接表或者邻接矩阵，二维表也可以for y,d in edge[x]:# 计算更新值，计算方式按照题目的意思new_dis = dx + d # 只有更优的值才能被加入进去if new_dis < dis[y]:dis[y] = new_disheapq.heappush(h,(new_dis,y))mx = max(dis)return mx if mx < float('inf') else -1

题目

743.网络延迟时间

743.网络延迟时间

思路分析：由于边的数量远远大于节点的数量，所以我们还是考虑使用稠密图下的朴素的Dijkstra算法，最后返回不是无穷的最大的路径即可

class Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:# 区别于BFS求解的最短距离，这个距离的边的权值不一样# 使用朴素的迪斯科特拉算法# 邻接矩阵记录边的情况edge = [[float('inf')]*(n) for _ in range(n)]# 有向边for e in times:edge[e[0]-1][e[1]-1] = e[2]dis = [float('inf')]*n # 记录k到各个节点的最短距离ans = dis[k-1] = 0done = [False] * n # 记录节点的最短距离是否被确定while True:x = -1# 找到最短距离还没确定，并且节点k到它的距离是最短的节点for i,ok in enumerate(done):if not ok and (x<0 or dis[i] < dis[x]):x = i # 如果x<0,表示全部的节点已经全部都访问过了if x < 0 :return ans# 如果最短的节点的距离是无穷，说明不可达if dis[x] == float('inf'):return -1# 更新ans = dis[x]done[x] = Truefor y,d in enumerate(edge[x]):dis[y] = min(dis[y],dis[x]+d)

使用堆优化的解法

import heapqclass Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:# 使用堆优化的Dijkstra算法# 使用堆优化的话，适用于稀疏图，所以边的记录，我们使用邻接表edge = [[] for _ in range(n)]for x,y,z in times:edge[x-1].append((y-1,z))dis = [float('inf')]*n dis[k-1] = 0# 入堆的元素是 (dis[x],x)h = [(0,k-1)]while h:dx,x = heapq.heappop(h)if dx > dis[x]:# 说明之前出过堆continuefor y,d in edge[x]:new_dis = dx + d if new_dis < dis[y]:dis[y] = new_disheapq.heappush(h,(new_dis,y))mx = max(dis)return mx if mx < float('inf') else -1

3341.到达最后一个房间的最少时间I

3341.到达最后一个房间的最少时间I

思路分析：开始的时候，我错误的以为题目中只能向右或者向下运动， 所以写了一个动态规划进行求解，实际上，这个思路是错误的,不过要是只能向下或者向右运动的话，动态规划也是一种很好的做法

# 动态规划的做法，竟然可以过700个测试用例
import heapq
class Solution:def minTimeToReach(self, moveTime: List[List[int]]) -> int:# 开始的时候从(0,0)出发，移动到相邻的房间，其实也只是向下或向右运动# 感觉可以用动态规划，dp[i][j]表示到达i,j所需的最少的时间# 递推公式，# dp[i][j] = min(max(dp[i-1][j],moveTime[i][j])+1,max(dp[i][j-1],moveTime[i][j])+1)n = len(moveTime)m = len(moveTime[0])dp = [[float('inf')]*(m+1) for _ in range(n+1)]dp[1][1] = 0for i in range(n):for j in range(m):if i == 0 and j == 0:continuedp[i+1][j+1] = min(max(dp[i][j+1],moveTime[i][j])+1,max(dp[i+1][j],moveTime[i][j])+1)for i in dp:print(i )return dp[n][m]

正确的思路：应该是使用Dijkstra算法，不过开始的时候，我有点纠结这个edge也就是边的矩阵如何转化为邻接矩阵或者邻接表，后面一想，还是我的固定思维阻碍了我，邻接矩阵和邻接表只是一个工具，帮助我们找到当前的节点的邻居，但是在现在的图中，你通过坐标的加减不就可以得到对应的邻居嘛！

• 展示使用朴素Dijkstra算法做法

import heapq
class Solution:def minTimeToReach(self, moveTime: List[List[int]]) -> int:# 首先先使用 堆优化的Dijkstra进行解题# 图已经构建，就是moveTime# dis[i][j]表示(0,0)到(i,j)的最短的时间n,m = len(moveTime),len(moveTime[0])dis = [[float('inf')]*m for _ in range(n)]dis[0][0] = 0done = [[False]*m for _ in range(n)]while True:x,y = -1,-1# 开始遍历还没确定的点for i in range(n):for j in range(m):if not done[i][j] and ((x<0 and y <0) or dis[i][j] < dis[x][y]):x,y = i,jif x<0 and y <0:# 说明都找到了return dis[n-1][m-1]# 设置已经找到done[x][y] = True# 访问邻居for i,j in (x+1,y),(x-1,y),(x,y+1),(x,y-1):if 0<= i < n and 0<= j < m:dis[i][j] = min(max(dis[x][y],moveTime[i][j]) + 1,dis[i][j])

• 展示使用堆优化的Dijkstra算法

import heapq
class Solution:def minTimeToReach(self, moveTime: List[List[int]]) -> int:# 首先先使用 堆优化的Dijkstra进行解题# 图已经构建，就是moveTime# dis[i][j]表示(0,0)到(i,j)的最短的时间n,m = len(moveTime),len(moveTime[0])dis = [[float('inf')]*m for _ in range(n)]dis[0][0] = 0h = [(0,0,0)]while True:d,x,y = heapq.heappop(h)if x == n-1 and y == m-1:return d # 已经更新过了if d > dis[x][y]:continue# 访问邻居：for i,j in (x+1,y),(x-1,y),(x,y+1),(x,y-1):if 0<= i <n and 0<= j < m:# 合法的坐标# 计算当前的距离，小于才入堆new_dis = max(d,moveTime[i][j])+1if dis[i][j]>new_dis:dis[i][j] = new_disheapq.heappush(h,(dis[i][j],i,j))