《庆余年算法番外篇》：范闲通过最短路径算法在阻止黑骑截杀林相

2024-06-01 15:20:49

剧情背景

在《庆余年 2》22集中，林相跟大宝交代完为人处世的人生哲理之后，就要跟大宝告别了

在《庆余年 2》23集中，林相在告老还乡的路上与婉儿和大宝告别后
范闲也在与婉儿的对话中知道黑骑调动是绝密，并把最近一次告老还乡梅执礼被马匪截杀与黑骑调动日期关联在一起，范闲知道了老皇帝要杀林相消息，所以范闲必须尽快找到一条最短路径在黑骑到之前去营救林相。这时候范闲在另外一个世界带来的记忆突然奔袭而来，马上想到用于地图导航GPS的Dijkstra算法，得找到路程最短的路径赶在黑骑到达前才能拯救林相，而在此之前他早就把庆国地形和路径都让人探究清楚了。知道黑骑所在位置到林相的位置大概需要75分钟。

现状输入描述

起点A：范闲目前所在的位置。
中点B：林相目前所在的位置。
节点集：A和B之间的多个节点路口CDEGF（例如路上的交叉点、村庄等）。
路程：连接这些节点的道路，每条道路有对应的行驶时间。

使用Dijkstra算法求解最短路径

实现原理

Dijkstra 算法从指定的节点（源节点）出发，寻找它与图中所有其它节点之间的最短路径。

Dijkstra 算法会记录当前已知的最短路径，并在寻找到更短的路径时更新。

一旦找到源节点与其他节点之间的最短路径，那个节点会被标记为“已访问”并添加到路径中。

重复寻找过程，直到图中所有节点都已经添加到路径中。这样，就可以得到从源节点出发访问所有其他节点的最短路径方案。

以下是详细的步骤和计算过程：

步骤 1: 初始化

起点A到所有其他节点的初始距离设为无穷大，除了起点本身，其距离为0。
使用优先队列初始化，从起点A开始。

距离:
A: 0
C: ∞
D: ∞
E: ∞
F: ∞
G: ∞
B: ∞

优先队列:
[(0, 'A')]

步骤 2: 处理节点A

从A出发，可以到C和D，更新距离。

步骤 3: 处理节点C

从C出发，可以到E，更新距离。

步骤 4: 处理节点D

从D出发，可以到E，但已有更短路径 C -> E，不更新。

距离:
A: 0
C: 15
D: 20
E: 25
F: ∞
G: ∞
B: ∞

优先队列:
[(25, 'E')]

步骤 5: 处理节点E

从E出发，可以到F和G，更新距离。

步骤 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，更新距离。

结果

通过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 因为没有导航刚刚手动计算已经花了两分钟了，情况紧急叫来王启年，马上赶路
王启年说范闲我们两个打不过黑骑，但是范闲说情况紧急没法给你找兵马，要去拼一把，跟打工人不给资源不给权利但是还要让你做出业绩一样、跟研究生不给钱不给署名还要写出论文一样

这里可以看出王启年作为一个优秀员工，肯定每年拿E，这表情比老板还急

从这里可以看出来，王启年业务能力也是一流，跑的比骑马快

按预期时间总算到了，开始正面刚黑骑

王启年虽然辛苦，但是范闲作为老板还是能抗事，马上承担责任，确保拿到结果，取得业绩有超强的领导力，是一个好老板

参考代码

import heapq

def dijkstra(graph, start):
    queue = [(0, start)]
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = 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}")

写到最后

希望文章能让大家放松的同时有知识进入到脑子里
这里作者祝大家：

高考\期末考的同学们：笔尖跃动光辉梦，心中理想定成真
毕业生们：才华扬帆乘风起，壮志凌云展未来
正在工作：不畏艰难勇向前，努力奋斗创佳绩
老板领导们：睿智领导拓新路，胸怀广阔业绩殊

码农公寓