[华为OD] 最小传输时延(dijkstra算法)

这篇具有很好参考价值的文章主要介绍了[华为OD] 最小传输时延(dijkstra算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

明天就要面试了我也太紧张了吧

但是终于找到了一个比较好理解的dijkstra的python解法,让我快点把它背下来!!!!

题目

先把题目放出来

某通信网络中有N个网络结点,用1到N进行标识。网络通过一个有向无环图表示,其中题的边的值表示结点之间的消息传递时延。现给定相连节点之间的时延列表 times[i] = {u,v,w},其中u表示源节点,v表示目的节点,w表示u和v之间的消息传递时延。
请计算给定源结点到目的结点的最小传输时延,如果目的结点不可达,返回-1。

输入描述:
输入的第一行为两个正整数,分别表示网络结点的个数N以及时延列表长度M,用空格分隔。
接下来的M行为两个结点间的时延列表[u,v,w]
输入的最后一行为两个正整数,分别表示源结点和目的结点。

比如:

输入 3 3
1 2 11
2 3 13
1 3 50
1 3
输出 24

一个有向无环图,用dfs也很好做。这里我们重点看一下dijkstra怎么做。

dijkstra算法的python实现

最短路径算法Dijkstra,主要思想是贪心。每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。
更具体地来说:
假设我们现在在一个有权图中,图中有n个点,点与点相连的路径上都分配有权重,代表了两点之间的距离。现在有一个起始点i,终点j,如果求i到j的最短距离。

  1. 我们建立一个集合s,把起始点i放进去,然后在与i相邻的边中寻找与i距离最近的点,并把这个点放到集合中去。
  2. 然后第二次遍历与集合中的点相连的点,并更新到起始点的距离,并把距离起始点i最近的点放到集合中去。
  3. 继续上面的做法,每次都在集合中添加一个点。直到没有新的点可以添加进去。

我们来写一个比较简单的python实现。
假设现在有n个节点,同时有一个输入distance距离列表,里面的元素表示的是[u,v,w]即u到v的距离。现在给定起点k,求k到最远的点的最小距离

dist = [float('inf')]*n # 构建一个列表存放n个结点到目标k的距离
dist[k-1] = 0  # 第k个结点到他本身的距离为0

g = [[float('inf')] * n for _ in range(n)] # 构建一个矩阵,表示n个结点彼此的距离。
for x, y, dis in distance:
	g[x-1][y-1] = time  # 按照distance列表更新矩阵中两两结点的距离。

used = [False]*n # 判断点是否已经加入了set里面。

for _ in range(n):
	x = -1
	for y, u in enumerate(used):
		if not u and (x == -1 or dist[y] < dist[x]): #只考虑没有使用过的节点,寻找结点们到初始点的最小距离。
		# 毫无疑问,在第一次遍历中,这个距离是0,目标点是我们的源点本身。
			x = y  # 如果距离小,就用新的点替换掉x。
		
	used[x] = True # 每次都使用距离源点最近的点
	for y, time in enumerate(g[x]):
		dist[y] = min(dist[y], dist[x]+time)  # 更新相连的结点到源点的距离

ans = max(dist)  # 这就是我们要求的k到最远的点的最小距离

dijkstra的时间复杂度是 O ( N 2 ) O(N^2) O(N2).

这个题也可以用dfs的方法来作,遍历到父结点时,更新所有的子结点到源点的距离。dfs解该题的时间复杂度更高一点,是 O ( N N ) O(N^N) O(NN).
同样给出一个解法代码。

map_dict = defaultdict(list)
for u, v, w in distance:
	map_dict[u].append([v,w])  

dist = [float('inf')] * n
def dfs(index, dis):
	if dis < dist[index-1]:
		dist[index-1] = dis
		for v, w in map_dict[index]:
			dfs(v,dis+w)
dfs(k,0)

res = max(dist)

python解答

我们回到题目的python解答上。

dfs解法

首先我们给出一个dfs的解答。
可以看到这个解法和上面的dfs几乎一模一样,区别是这里返回的是源节点到目标点的距离。

def solution(times,src, dist):
    graph = {}
    for u,v, w in times:
        if u not in graph:
            graph[u] = []
        graph[u].append([v,w])
    
    root = [float('inf')]*N    
    def dfs(index, dis):
        
        if dis<root[index-1]:
            root[index-1] = dis
            if index in graph:
                for u, v in graph[index]:
                    dfs(u,dis+v)
                
    dfs(src,0)
    res = root[dist-1]
    return res if res!=float('inf') else -1
    

dijkstra解法

这个解法也是和上面的思路一样,只不过在发现x==dis-1的时候,提前break结束了这个循环。文章来源地址https://www.toymoban.com/news/detail-614754.html

def solution(times, src, dis):
    g = [[float('inf')]*N for _ in range(N)]
    for u,v, time in times:
        g[u-1][v-1] = time
        
    dist = [float('inf')]*N
    dist[src-1] = 0
    used = [False]*N
    for i in range(N):
        x = -1
        for y, u in enumerate(used):
            if not u and (x==-1 or dist[y]< dist[x]):
                x = y
        if x == dis-1:
            break
        used[x] = True
        for y, time in enumerate(g[x]):
            dist[y] = min(dist[y],dist[x]+time)
            
    return dist[dis-1]

到了这里,关于[华为OD] 最小传输时延(dijkstra算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 255.【华为OD机试】最小矩阵宽度(滑动窗口算法-Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年03月13日
    浏览(64)
  • 华为OD机试 - 求最小步数(Java & JS & Python)

    题目描述 求从坐标零点到坐标点n的最小步数,一次只能沿横坐标轴向左或向右移动 2 或 3。 注意:途径的坐标点可以为负数 输入描述 坐标点n 输出描述 输出从坐标零点移动到坐标点n的最小步数 备注 1 = n = 10^9 用例 输入 4 输出 2 说明 从坐标零点移动到4,最小需要两步,即

    2024年02月13日
    浏览(45)
  • 华为OD机试 - 最小循环子数组(Java & JS & Python)

    题目描述 给定一个由若干整数组成的数组nums,请检查数组是否是由某个子数组重复循环拼接而成,请输出这个最小的子数组。 输入描述 第一行输入数组中元素个数n,1 ≤ n ≤ 100000 第二行输入数组的数字序列nums,以空格分割,0 ≤ nums[i]  10 输出描述 输出最小的子数组的数

    2024年02月12日
    浏览(53)
  • 华为OD机试 - 最小矩阵宽度(Java & JS & Python & C)

    题目描述 给定一个矩阵,包含 N * M 个整数,和一个包含 K 个整数的数组。 现在要求在这个矩阵中找一个宽度最小的子矩阵,要求子矩阵包含数组中所有的整数。 输入描述 第一行输入两个正整数 N,M,表示矩阵大小。 接下来 N 行 M 列表示矩阵内容。 下一行包含一个正整数

    2024年01月23日
    浏览(58)
  • 华为OD机试 - 等和子数组最小和(Java & JS & Python)

    题目描述 给定一个数组nums,将元素分为若干个组,使得每组和相等,求出满足条件的所有分组中,组内元素和的最小值。 输入描述 第一行输入 m 接着输入m个数,表示此数组nums 数据范围:1=m=50, 1=nums[i]=50 输出描述 最小拆分数组和 用例 输入 7 4 3 2 3 5 2 1 输出 5 说明 可以等分

    2024年02月04日
    浏览(51)
  • 华为OD机试 - 最小调整顺序次数、特异性双端队列(Python)

    有一个特异性的双端队列,该队列可以从头部或尾部添加数据,但是只能从头部移出数据。 小A依次执行2n个指令往队列中添加数据和移出数据。其中n个指令是添加数据(可能从头部添加、也可能从尾部添加),依次添加1到n;n个指令是移出数据。 现在要求移除数据的顺序为

    2024年02月02日
    浏览(37)
  • 【华为OD】C卷真题 200分:最小矩阵宽度 python代码实现[思路+代码]

    C++、java、JS代码: 【华为OD】C卷真题 200分:最小矩阵宽度 C/C++代码实现[思路+代码]-CSDN博客 【华为OD】C卷真题 200分:最小矩阵宽度 Java代码实现[思路+代码]-CSDN博客 【华为OD】C卷真题 200分:最小矩阵宽度 JavaScript代码实现[思路+代码]-CSDN博客  给定一个矩阵,包含N*M个整数,

    2024年04月17日
    浏览(65)
  • 华为OD机试 - 等和子数组最小和(Java & JS & Python & C & C++)

    哈喽,本题库完全免费,收费是为了防止被爬,大家订阅专栏后可以私信联系退款。感谢支持 给定一个数组nums,将元素分为若干个组,使得每组和相等,求出满足条件的所有分组中,组内元素和的最小值。 第一行输入 m 接着输入m个数,表示此数组nums 数据范围:1=m=50, 1=nu

    2024年03月27日
    浏览(54)
  • 【免费题库】华为OD机试 - 组合出合法最小数(Java & JS & Python & C & C++)

    哈喽,本题库完全免费,收费是为了防止被爬,大家订阅专栏后可以私信联系退款。感谢支持 给一个数组,数组里面哦都是代表非负整数的字符串,将数组里所有的数值排列组合 Q 拼接起来组成一个数字,输出拼接成的最小的数字。 个数组,数组不为空,数组里面都是代表

    2024年04月11日
    浏览(70)
  • 【华为OD统一考试B卷 | 100分】求最小步数(C++ Java JavaScript Python)

    在线OJ 已购买本专栏用户,请私信博主开通账号,在线刷题!!! 运行出现 Runtime Error 0Aborted,请忽略 华为OD统一考试A卷+B卷 新题库说明 2023年5月份,华为官方已经将的 2022/0223Q(1/2/3/4)统一修改为OD统一考试(A卷)和OD统一考试(B卷)。 你收到的链接上面会标注A卷还是B卷。

    2024年02月15日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包