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

news/2025/2/22 15:20:01

文章目录

  • 题目
    • 743.网络延迟时间
    • 3341.到达最后一个房间的最少时间I

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

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

朴素的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))

http://www.niftyadmin.cn/n/5862443.html

相关文章

Linux自学day24-进程和线程2

Linux自学day24-进程和线程2

一 进程结束 这段代码的主要功能是创建一个子进程&#xff0c;子进程休眠 10 秒后以退出状态码 10 结束&#xff0c;父进程等待子进程结束并回收其资源&#xff0c;同时根据子进程的退出状态输出相应的信息。 int main(int argc, const char **argv) {// 定义一个 pid_t 类…
阅读更多...
飞书API

飞书API

extend目录下,API <?php // ---------------------------------------------------------------------- // | 飞书API // ---------------------------------------------------------------------- // | COPYRIGHT (C) 2021 http://www.jeoshi.com All rights reserved. …
阅读更多...
电商API安全防护：JWT令牌与XSS防御实战

电商API安全防护：JWT令牌与XSS防御实战

在电商 API 的安全防护中&#xff0c;JWT&#xff08;JSON Web Token&#xff09;令牌用于身份验证和授权&#xff0c;而 XSS&#xff08;跨站脚本攻击&#xff09;防御则是防止恶意脚本注入&#xff0c;保护用户数据和系统安全。以下是这两方面的实战介绍。 JWT 令牌实战 1. 生…
阅读更多...
flowable适配达梦数据库

flowable适配达梦数据库

文章目录 适配相关问题无法从数据库产品名称“DM DBMS”中推断数据库类型分析解决 构建ibatis SqlSessionFactory时出错&#xff1a;inStream参数为null分析解决 liquibase相关问题问题一&#xff1a;不支持的数据库 Error executing SQL call current_schema: 无法解析的成员访…
阅读更多...
网络安全-Mysql注入知识点

网络安全-Mysql注入知识点

本篇文章介绍sql注入时数据库是Mysql时需要掌握的知识点。以Navicat、mysql 5.7.4为例。 注释 #或--空格是单行注释 /**/是内联注释 SQL语句 查询语句 SELECT〈目标列组〉 FROM〈数据源〉 [WHERE〈元组选择条件〉] [GROUP BY〈分列组〉[HAVING 〈组选择条件…
阅读更多...
MySql面试宝典【刷题系列】

MySql面试宝典【刷题系列】

文章目录 一、Mysql 的存储引擎 myisam 和 innodb 的区别。二、MySQL数据库作发布系统的存储&#xff0c;一天五万条以上的增量&#xff0c;预计运维三年,怎么优化&#xff1f;三、对于大流量的网站,您采用什么样的方法来解决各页面访问量统计问题&#xff1f;四、锁的优化策略…
阅读更多...
代码随想录算法训练day59---图论系列4

代码随想录算法训练day59---图论系列4

代码随想录算法训练 —day59 文章目录 代码随想录算法训练前言一、110.字符串接龙二、105.有向图的完全可达性dfs版本1dfs版本2bfs版本 三、100. 岛屿的最大面积方法一方法二 总结 前言 今天是算法营的第59天&#xff0c;希望自己能够坚持下来&#xff01; 今天继续图论part&…
阅读更多...
工控自动化领域：数字量信号与模拟量信号的差异解析

工控自动化领域：数字量信号与模拟量信号的差异解析

在工控自动化的神秘世界里&#xff0c;信号如同传递指令和信息的使者&#xff0c;而数字量信号和模拟量信号则是其中的两大主角。它们各自有着独特的 “性格” 和 “使命”&#xff0c;在不同的场景中发挥着关键作用。下面&#xff0c;就让我们一起来深入了解一下它们的区别。 …
阅读更多...
最新文章

Copyright @ 2022~2023