文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

怎么使用Dijkstra算法

2024-04-02 19:55

关注

怎么使用Dijkstra算法,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。

最短路问题

最短路问题(Shortest Path  Problems):给定一个网络,网络的边上有权重,找一条从给定起点到给定终点的路径使路径上的边权重总和最小。

最短路问题常用Dijkstra算法解决

Dijkstra算法

Dijkstra算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

比如,上图Dijkstra算法就是不断地寻找开始节点到邻居节点的所有的路径,将最初的距离设置为最短距离,然后不断的更新节邻居节点的最短距离,直到最远的节点的最短距离求解出来的过程。

文字描述不清楚,看下面的动图。

怎么使用Dijkstra算法

将图上的顶点分为已访问visited和未访问node两个集合。

每次从visited向外拓展一个点,拓展规则是在可更新的点里是距离最小的。

我们还是以上面的图为例

怎么使用Dijkstra算法

先用邻接矩阵表示无向图:

MAX = 9999  g= [     [0, 1, 4, 6],     [MAX, 0, MAX, 2],     [MAX, MAX, 0, 1],     [MAX, MAX, MAX, 0] ]

邻接矩阵g[0][1]=1表示,第一个节点到第二个节点的距离是1。

目的是要求出开始点1到其他各个点的最小路径距离

n = 4 #4个点 # 初始化 visited  visitd = [0] * (n) #记录该点是否为访问过 # 第一个点已经访问了 visitd[0] = 1 #初始化源点到各个点的距离 node 集合 d = g[0]  for i in range(2, n):     # 遍历d 取出权重最小节点的位置     minWeigth = MAX     for j in range(2, n):         if d[j] < minWeigth and visitd[j] == 0:             minWeigth = d[j]             k = j             # 表示k是当前距1最短的点,同时标记k已经被找过     visitd[k] = 1     #  用该点进行松弛(relax)     for j in range(2, n):         if d[j] > d[k] + g[k][j] and visitd[j] == 0:             d[j] = d[k] + g[k][j]  for i in range(1,n):     print(d[i])      1 4 5

至此,得到节点1到其余三个节点的最短距离是1、4和5。

「把Dijkstra 算法应用于无权图,或者所有边的权都相等的图,Dijkstra 算法等同于BFS搜索。」

多点求解

在很多的时候,要求输入一组点,然后求出输入一个起始点,得到无向图最短路径。

import math # 假设图中的顶点数 V = 6 # 标记数组:used[v]值为False说明改顶点还没有访问过,在S中,否则在U中! used = [False for _ in range(V)] # 距离数组:distance[i]表示从源点s到i的最短距离,distance[s]=0 distance = [float('inf') for _ in range(V)] # cost[u][v]表示边e=(u,v)的权值,不存在时设为INF # cost领接表 cost = [[float('inf') for _ in range(V)] for _ in range(V)]  def dijkstra(s):     distance[s] = 0     while True:         # v在这里相当于是一个哨兵,对包含起点s做统一处理!         v = -1         # 从未使用过的顶点中选择一个距离最小的顶点         for u in range(V):             if not used[u] and (v == -1 or distance[u] < distance[v]):                 v = u         if v == -1:             # 说明所有顶点都维护到S中了!             break         # 将选定的顶点加入到S中, 同时进行距离更新         used[v] = True         # 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。         for u in range(V):             distance[u] = min(distance[u], distance[v] + cost[v][u])   for _ in range(9):     v, u, w = list(map(int, input().split()))     cost[v][u] = w     cost[u][v] = w s = int(input('请输入一个起始点:')) dijkstra(s) print(distance)

测试用例

0 1 1 0 2 2 0 3 3 1 4 7 1 5 9 2 4 4 3 4 5 3 5 6 4 5 8 请输入一个起始点:0 [0, 1, 2, 3, 6, 9]

在测试用例中的0 1 1表示第一个顶点到第二个顶点的距离是1。

Dijkstra算法使用邻接表的时间复杂度是怎么使用Dijkstra算法。因此,很多使用堆进行优化或者使用散列表对多余的空间进行优化。

看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注编程网行业资讯频道,感谢您对编程网的支持。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-前端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯