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

求解最短路径的问题，分为使用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 = -1
	for 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 heapq

class 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_dis
                    heapq.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] = 0
        done = [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] = True
            for y,d in enumerate(edge[x]):
                dis[y] = min(dis[y],dis[x]+d)

使用堆优化的解法

import heapq

class 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_dis
                    heapq.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] = 0
        for i in range(n):
            for j in range(m):
                if i == 0 and j == 0:
                    continue
                dp[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] = 0
        done = [[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,j
            if 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] = 0
        h = [(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])+1
                    if dis[i][j]>new_dis:
                        dis[i][j] = new_dis
                        heapq.heappush(h,(dis[i][j],i,j))