《庆余年算法番外篇》：范闲通过最短路径算法在阻止黑骑截杀林相
剧情背景在《庆余年 2》22集中，林相跟大宝交代完为人处世的人生哲理之后，就要跟大宝告别了
https://img-blog.csdnimg.cn/direct/a2293a607f5a4b9c9eba04d9a2591d62.png
在《庆余年 2》23集中，林相在告老还乡的路上与婉儿和大宝告别后https://img-blog.csdnimg.cn/direct/5f2bfb0bf763447e80c41615d0703d92.png
范闲也在与婉儿的对话中知道黑骑变更是绝密，并把近来一次告老还乡梅执礼被马匪截杀与黑骑变更日期关联在一起，范闲知道了老皇帝要杀林相消息，所以范闲必须尽快找到一条最短路径在黑骑到之前往营救林相。这时间范闲在别的一个世界带来的影象突然奔袭而来，立刻想到用于地图导航GPS的Dijkstra算法，得找到路程最短的路径赶在黑骑到达前才气救济林相，而在此之前他早就把庆国地形和路径都让人探究清楚了。知道黑骑所在位置到林相的位置大概需要75分钟。
现状输入描述
[*]起点A：范闲目前所在的位置。
[*]中点B：林相目前所在的位置。
[*]节点集：A和B之间的多个节点路口CDEGF（比方路上的交织点、乡村等）。
[*]路程：毗连这些节点的道路，每条道路有对应的行驶时间。
https://img-blog.csdnimg.cn/direct/67171195176648ce912d708fd2b0794f.png
利用Dijkstra算法求解最短路径
实现原理
[*]Dijkstra 算法从指定的节点（源节点）出发，寻找它与图中所有其它节点之间的最短路径。
[*]Dijkstra 算法会记录当前已知的最短路径，并在寻找到更短的路径时更新。
[*]一旦找到源节点与其他节点之间的最短路径，那个节点会被标记为“已访问”并添加到路径中。
[*]重复寻找过程，直到图中所有节点都已经添加到路径中。这样，就可以得到从源节点出发访问所有其他节点的最短路径方案。
以下是详细的步骤和计算过程：
步骤 1: 初始化
[*]起点A到所有其他节点的初始间隔设为无穷大，除了起点自己，其间隔为0。
[*]利用优先队列初始化，从起点A开始。
距离:
A: 0
C: ∞
D: ∞
E: ∞
F: ∞
G: ∞
B: ∞
优先队列:
[(0, 'A')]
步骤 2: 处理节点A
[*]从A出发，可以到C和D，更新间隔。
https://img-blog.csdnimg.cn/direct/9201f038807e46b88ace900ccb411d41.png
步骤 3: 处理节点C
[*]从C出发，可以到E，更新间隔。
https://img-blog.csdnimg.cn/direct/92598615adb448e5aa11ac6a57f715cb.png
步骤 4: 处理节点D
[*]从D出发，可以到E，但已有更短路径 C -> E，不更新。
距离:
A: 0
C: 15
D: 20
E: 25
F: ∞
G: ∞
B: ∞
优先队列:
[(25, 'E')]
步骤 5: 处理节点E
[*]从E出发，可以到F和G，更新间隔。
https://img-blog.csdnimg.cn/direct/7a26ed5fee484b1082ad127abfe3a1aa.png
步骤 6: 处理节点F
[*]从F出发，可以到B，更新间隔。
距离:
A: 0
C: 15
D: 20
E: 25
F: 43
G: 45
B: 88
优先队列:
[(45, 'G'), (88, 'B')]
步骤 7: 处理节点G
[*]从G出发，可以到B，更新间隔。
https://img-blog.csdnimg.cn/direct/3705d8408e3b4ef28eba2be4854d776e.png
效果
通过Dijkstra算法计算，范闲从A到B的最短路径是A -> C -> E -> G -> B，总时间为：
[*]A -> C：15分钟
[*]C -> E：10分钟
[*]E -> G：20分钟
[*]G -> B：25分钟
[*]总时间：15 + 10 + 20 + 25 = 70分钟 (黑骑到林相需要75分钟)
这时间选择A -> C -> E -> G -> B 因为没有导航刚刚手动计算已经花了两分钟了，情况告急叫来王启年，立刻赶路
王启年说范闲我们两个打不过黑骑，但是范闲说情况告急没法给你找兵马，要去拼一把，跟打工人不给资源不给权利但是还要让你做出业绩一样、跟研究生不给钱不给署名还要写出论文一样
https://img-blog.csdnimg.cn/direct/e86410ded451460dbf818e0fd5eb4f3e.png
这里可以看出王启年作为一个良好员工，肯定每年拿E，这心情比老板还急
https://img-blog.csdnimg.cn/direct/75299f09a1c74cfc94e9df7e56edf2f9.png
从这里可以看出来，王启年业务本领也是一流，跑的比骑马快
https://img-blog.csdnimg.cn/direct/b4bfc9fbe3a8405b90e8c033748a73f3.png
按预期时间总算到了，开始正面刚黑骑
https://img-blog.csdnimg.cn/direct/e73c1bceb2e84486b403a00a3a66e95f.png
王启年虽然辛苦，但是范闲作为老板照旧能抗事，立刻承担责任，确保拿到效果，取得业绩有超强的领导力，是一个好老板
https://img-blog.csdnimg.cn/direct/36441a77f927437a828df03d33748c4e.png
参考代码
import heapq
def dijkstra(graph, start):
queue = [(0, start)]
distances = {node: float('inf') for node in graph}
distances = 0
while queue:
current_distance, current_node = heapq.heappop(queue)
if current_distance > distances:
continue
for neighbor, weight in graph.items():
distance = current_distance + weight
if distance < distances:
distances = distance
heapq.heappush(queue, (distance, neighbor))
return distances
# 图的邻接表表示
graph = {
'A': {'C': 15, 'D': 20},
'C': {'A': 15, 'E': 10},
'D': {'A': 20, 'E': 15},
'E': {'C': 10, 'D': 15, 'F': 18, 'G': 20},
'F': {'E': 18, 'B': 45},
'G': {'E': 20, 'B': 25},
'B': {'F': 45, 'G': 25}
}
# 计算从起点A到各节点的最短路径
start = 'A'
distances = dijkstra(graph, start)
print(f"从{start}到各节点的最短路径: {distances}")
写到最后
希望文章能让大家放松的同时有知识进入到脑子里
这里作者祝大家：
[*]高考\期末考的同学们：笔尖跃动光辉梦，心中抱负定成真
[*]毕业生们：才气扬帆乘风起，壮志凌云展将来
[*]正在工作：不畏困难勇向前，努力奋斗创佳绩
[*]老板领导们：睿智领导拓新路，胸怀广阔业绩殊
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]