❤️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)#找出接下来要处理的节点,并循环
🌲🌲🌲 好啦,这就是今天要分享给大家的全部内容了
❤️❤️❤️如果你喜欢的话,就不要吝惜你的一键三连了~
- 点赞
- 收藏
- 关注作者
评论(0)