❤️Python分而治之❤️ 算法图解:第七章:狄克斯特拉算法

举报
是Dream呀 发表于 2022/01/15 12:49:29 2022/01/15
【摘要】 ❤️Python分而治之❤️ 算法图解:第七章:狄克斯特拉算法

📢📢📢📣📣📣
🌻🌻🌻Hello,大家好我叫是Dream呀,一个有趣的Python博主,小白一枚,多多关照😜😜😜
🏅🏅🏅CSDN Python领域新星创作者,大二在读,欢迎大家找我合作学习
💕入门须知:这片乐园从不缺乏天才,努力才是你的最终入场券!🚀🚀🚀
💓最后,愿我们都能在看不到的地方闪闪发光,一起加油进步🍺🍺🍺
🍉🍉🍉“一万次悲伤,依然会有Dream,我一直在最温暖的地方等你”,唱的就是我!哈哈哈~🌈🌈🌈
🌟🌟🌟✨✨✨

@TOC
广度优先搜索用于找出段数最少的路径,如果你要找出最快的路径,该咋办呢?需要用到另一种算法:狄克斯特拉算法。

7.1使用狄克斯特拉算法

四个步骤:
1.找出“最便宜”的节点,即在最短的时间内到达的节点。
2.更新该节点的邻居的开销,其含义稍后介绍。
3.重复这个计算过程,直到对图中的每个节点都这样做了。
4.计算最终路径。

第一步:找出最便宜的节点。你站在起点,不知道该前往节点A还是前往节点B。前往这两个节点需要多少时间呢?
把前往终点时间定义为无限大,你会发现只看一步的话到B最近;

第二步:计算节点B前往其各个邻居所需要的时间。突然你又发现了一条经B到A更近的路,这样对于经B的邻居A而言,如果找到前往他的更短路径,就更新其开销。

第三步:重复!
重复第一步(找出可在最短时间内前往的节点)和第二步(更新节点A的所有邻居的开销)

最后一步:计算最终的路径。

7.2术语

狄克斯特拉算法用于每条边都有关联数字的图,这些数字称为权重。带权重的图称为加权图,不带权重的图称为非加权图
无向图意味着两个节点彼此指向对方,其实就是环!在无向图中,每条边都是一个环。 狄克斯特拉算法只适用于 有向无环图

7.3负权边

如果有负权边,就不能使用狄克斯特拉算法。因为负权边会导致这种算法不管用。根据狄克斯特拉算法,没有比不支付任何费用获得海报更便宜的方式。(你知道这是不对的!)
有负权边问题时,书上说可以用另一种算法来实现:贝尔曼——福德算法,但是它没讲,差评!!!

7.4实现

1.首先创建一个散列表:

graph={}
graph["you"]=['alice', 'bob','claiure']

但这里需要需要同时储存邻居和前往邻居的开销。例如:起点有两个邻居——A和B
2.表示这些边的权重

graph['start']={}
graph['start']['a']=6
graph['start']['b']=2

3.下面添加其他节点和邻居:

graph['a']={}
graph['a']['fin']=1
graph['b']={}
graph['b']['a']=3
graph['b']['fin']=5
graph["fin"]={}#终点没有任何邻居

对不知道的开销,可以将其设置为无穷大:

infinity=float('inf')

4.创建开销表:

infinity=float('inf')
costs={}
costs['a']=6
costs['b']=2
costs['fin']=infinity

5.创建储存父节点的散列表:

parents={}
parents['a']='start'
parents['b']='start'
parents['fin']=None

6.创建一个数组,存储记录处理过的节点:

processed=[]

7.找出开销最低的节点:

def find_lowest_cost_node(costs):
    lowest_cost=float('inf')
    lowest_cost_node=None
    for node in costs:
        cost =costs[node]
        if cost<lowest_cost and node not in processed:
            lowest_cost=cost
            lowest_cost_node=node
    return lowest_cost_node

8.最终实现:

node=find_lowest_cost_node(costs)#在未处理的节点中找出开销最小的点
while node is not None:#这个while循环在所有节点都被处理过后结束
    cost=costs[node]
    neighbors=graph[node]
    for n in neighbors.keys():#遍历当前节点的所有邻居
        new_cost=cost+neighbors[n]
        if costs[n]>new_cost:#如果经当前节点前往该邻居更近
            costs[n]=new_cost#就更新其邻居开销
            parents[n]=node#同时将该邻居的父点设置为当前节点
        processed.append(node)#将当前的节点标记为处理过
        node=find_lowest_cost_node(costs)#找出接下来要处理的节点,并循环

🌲🌲🌲 好啦,这就是今天要分享给大家的全部内容了
❤️❤️❤️如果你喜欢的话,就不要吝惜你的一键三连了~在这里插入图片描述

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。