📢📢📢📣📣📣
🌻🌻🌻Hello，大家好我叫是Dream呀，一个有趣的Python博主，小白一枚，多多关照😜😜😜
🏅🏅🏅CSDN Python领域新星创作者，大二在读，欢迎大家找我合作学习
💕入门须知：这片乐园从不缺乏天才，努力才是你的最终入场券！🚀🚀🚀
💓最后，愿我们都能在看不到的地方闪闪发光，一起加油进步🍺🍺🍺
🍉🍉🍉“一万次悲伤，依然会有Dream，我一直在最温暖的地方等你”，唱的就是我！哈哈哈~🌈🌈🌈
🌟🌟🌟???
第七章：狄克斯特拉算法
广度优先搜索用于找出段数最少的路径，如果你要找出最快的路径，该咋办呢？需要用到另一种算法：狄克斯特拉算法。
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)#找出接下来要处理的节点，并循环
📢📢📢最后的福利
🍋🍋🍋最后一点小福利带给大家：如果想快速上手python的小伙伴们，这个详细整理PPT可以迅速帮助大家打牢python基础，需要的小伙伴们可以下载一下 Python入门基础教程全套+小白速成+学不会来找我！ 🍻🍻🍻
还有自制表白神器，需要自取：
Python表白神器，源码+解析+各种完美配置+浪漫新颖 🍻🍻🍻
🌲🌲🌲 好啦，这就是今天要分享给大家的全部内容了
??????如果你喜欢的话，就不要吝惜你的一键三连了~