第十二届蓝桥杯试题E 最短路径 Python 狄克斯特拉解法 超详细

简介: 第十二届蓝桥杯试题E 最短路径 Python 狄克斯特拉解法 超详细

导语:

       距离蓝桥杯比赛还有75天 和小郑一起加油

问题描述:

f71eb2428e024cdea70bbce19a568531.png 考察知识点:狄克斯特拉算法+最小公倍数

不妨先看看如何求最小公倍数:

def lcm(a,b):#求最小公倍数
    s=a*b
    while b:
        a,b=b,a%b
    return int(s/a)


对于自然数a,b 最小公倍数*最大公倍数=ab 因此求出最大公倍数即可 而求最大公倍数可以使用辗转相除法


来到狄克斯特拉算法: 算法用于解决最短带权路径问题 如果你不会使用字典,建议先去掌握一下字典的基本用法再来读下面的文字~


a2a80e69098e4f7a9ea6a1616385e0ef.jpg


以上面这副图为例子 从起点到终点一共有三种路径


起点>>A>>终点 路径长度6+1=7


起点>>B>>终点 路径长度2+5=7


起点>>B>>A>>终点 路径长度2+3+1=6


显然 最短路径是6 因而 如果我们知道了所有节点的关系 就可把所有的路径长度列出来 取最小即可


但是这样 太过复杂 所以我们引入了狄克斯特拉算法


狄克斯特拉算法包括四个步骤:


(1)找出最便宜的节点P (这么说有点抽象 其实是可以这样想 把连接节点的边 对应的权值比作需要花费的金钱,也就是找出一个花最少的钱能够去的节点)


(2)对于节点P,研究它的邻居,检查是否有前往他们更短的路径,有就更新 (更新除了要更新路径 还要更新父节点,父节点这里不理解没事,后面会在提到😀)没有就不变


(3)记录这一轮的节点P(作为处理过的节点),对未处理过的节点重复(1)(2),直至所有节点都被处理过


(4)计算最终路径


以上面这幅图为例 我们需要创建字典graph,costs,parent,以及准备一个保存已处理的列表


用途:graph用来保存 每个节点和每个节点邻居以及节点到节点邻居的费用


graph={}
graph['start']={'A':6,'B':2}
graph['A']={'end':1}
graph['B']={'A':3,'end':5}
graph['end']={}
#结果:{'start': {'A': 6, 'B': 2}, 'A': {'end': 1}, 'B': {'A': 3, 'end': 5}, 'end': {}}

cost用来保存前往某个节点花费的钱(最少),由于我们并不知道前往终点最少要花费多少钱,假设为正无穷

cost={}
cost['A']=6
cost['B']=2
cost['end']=float('inf')#表示无穷大

parent用来保存父节点,由于我们并不知道终点的父节点是谁,假设为None(你可能会问 图上不是很明显父节点是A B吗?是的没错,但是你回到前面的四步骤看看,父节点的更新是需要伴随着最短路径的更新,由于我们并不知道前往终点的最短路径,所以暂且假设为None)

parent={}
parent['A']='start'
parent['B']='start'
parent['end']=None

下面呈现代码:

graph={}
graph['start']={'A':6,'B':2}
graph['A']={'end':1}
graph['B']={'A':3,'end':5}
graph['end']={}
cost={}
cost['A']=6
cost['B']=2
cost['end']=float('inf')#表示无穷大
parent={}
parent['A']='start'
parent['B']='start'
parent['end']=None
already=[]
def most_cheap(cost):
    most_cheap,most_cheap_node=float('inf'),None
    for node in cost.keys():
        costs=cost[node]
        if costs<most_cheap and node not in already:
            most_cheap,most_cheap_node=costs,node
    return most_cheap_node
node=most_cheap(cost)#从未处理过的节点中找出最便宜的节点
while node:#只要还有未处理的节点就执行
    costs=cost[node]#起点到该节点的最短开销
    neighbor=graph[node]#传入邻居以及当前节点到邻居的开销
    for i in neighbor.keys():#遍历所有邻居
        new_cost=costs+neighbor[i]#新开销
        if new_cost<cost[i]:
            cost[i]=new_cost#更新开销
            parent[i]=node#随之更新父节点
    already.append(node)#记录处理过的节点
    node=most_cheap(cost)#循环执行

输出结果 符合预期  

1. >>> cost
2. {'A': 5, 'B': 2, 'end': 6}


如果懂了上面这个例题的你再来处理蓝桥杯这道题就不会那么难了


根据题目意思 给出一个数字a 与他连接的数字包括[a+1,a+21]  与上面例题不同在于:邻居变多了


其次题目说是无向边 无向图意味着两个节点彼此指着对方 双向互通 而狄克斯特拉算法只适用于有向无环图 但是 本题依然可以使用狄克斯特拉算法 原因在于 要求最短路径势必每条边至多走一次 如果最短路径中存在有条边走了两次 意味着第二次行走的时候回到了还未走之前的节点 然后继续行走 那完全可以直接不走在一开始!因而每条边最多只能走一次


下面用狄克斯特拉算法解决本题:小郑自己写的 并且答案对了 (标准答案是10266837)

#狄克斯特拉算法
#字典 cost,graph,parents
#1:找到最便宜的结点(未访问),其邻居开销如有更小,更新(cost,parent)
def lcm(a,b):
    s=a*b
    while b:
        a,b=b,a%b
    return int(s/a)
graph={}#构图
costs={}
parent={}
for i in range(1,2022):
    graph[i]={}
    if i<=2020:
        for j in range(i+1,i+22):
            graph[i][j]=lcm(i,j)
    else:
        for j in range(i+1,2022):
             graph[i][j]=lcm(i,j)
    costs[i]=float('inf')
found=[]#查找过的结点
costs[1]=0#开始点w为最便宜的点,价格为0
def find(dict):#查找最便宜的结点
    node,cost=None,float('inf')
    for k,v in dict.items():
        if k not in found and v<cost:
            node,cost=k,v
    return node
node=find(costs)
while node:
    spend=costs[node]
    friend=graph[node]
    try:
        for i in friend.keys():
            if costs[i]>friend[i]+costs[node]:
                costs[i]=friend[i]+costs[node]
                parent[i]=node
    except:#无邻居,costs会报错,说明已经达到终点,打印即可
        print(costs[2021])
        break
    found.append(node)
    node=find(costs)
end=parent[2021]#回溯广搜层数
count=1
while end!=1:
    count+=1
    end=parent[end]
print(count)
#路径长度10266837,回溯了97次

本题具有一定难度 需要反复斟酌 我是小郑 在备战蓝桥杯的路上 希望和你一起加油!

对于本题还有动态规划解法 小郑还没想过 ~不过很快就会再出一篇啦


相关文章
|
5天前
|
存储 算法 数据挖掘
高效搜索技巧:最小覆盖子串解法【力扣75题 python】
高效搜索技巧:最小覆盖子串解法【力扣75题 python】
|
6天前
|
存储 机器学习/深度学习 算法
皇后之战:揭秘N皇后问题的多维解法与智慧【python 力扣52题】
皇后之战:揭秘N皇后问题的多维解法与智慧【python 力扣52题】
|
6天前
|
SQL 算法 数据挖掘
探索有效括号 力扣第20题:从栈到递归的多角度解法 【含图解 python】
探索有效括号 力扣第20题:从栈到递归的多角度解法 【含图解 python】
|
24天前
|
机器学习/深度学习 人工智能 算法
2024 蓝桥杯本科B组试题
2024 蓝桥杯本科B组试题
15 0
|
1月前
|
算法 机器人 Python
Python实现教程:平面最短路径算法
Python实现教程:平面最短路径算法
20 1
|
1月前
|
机器学习/深度学习 算法 定位技术
python中使用马尔可夫决策过程(MDP)动态编程来解决最短路径强化学习问题
python中使用马尔可夫决策过程(MDP)动态编程来解决最短路径强化学习问题
|
1月前
|
存储 人工智能 定位技术
千帆杯第一期赛题:游乐场排队规划助手(香港迪士尼python解法)
千帆杯第一期赛题:游乐场排队规划助手(香港迪士尼python解法)
87 0
|
1月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-940 试题3971
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-940 试题3971
33 0
|
1月前
|
Java C++ Python
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
33 0
|
1月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 十六进制转八进制
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 十六进制转八进制
25 0