【最短路--Yen(无重复K最短路) + Python】

文章目录

• • 1.前言
  • 2.代码实现
  • 3.优化方向
  • 4.参考资源

1.前言

最近在学习《交通网络均衡理论》这门课，我计划将其中的一些经典算法用Python实现，而后发布到这里来和大家交流，欢迎指正。

2.代码实现

'''
@Author: Michael 2022-09-16 21:57:27
This code is about Yen.'''from Dijkstra import Dijkstra
import copydef Short_limit(mgraph, inf, start, end, passed:list, noaccess:list):'''mgraph 为临界距离矩阵(以列表储存)inf    为设置的极大值passed 为当前必须经过点nopass 为当前禁止通行路段，以列表储存，其元素为二维列表，表示禁止通行的路段path   为当前条件下最短路径，以列表储存dis  为当前条件下最短路长度此处start,end,passed,noaccess均为现实标号'''mgraph_copy_1 = copy.deepcopy(mgraph)mgraph_copy_2 = copy.deepcopy(mgraph)if len(passed) != 0:start = passed[-1]for i,j in noaccess:mgraph_copy_2[i-1][j-1] = inffor i in passed:for j in range(len(mgraph)):#此步保证无重复点if i != passed[-1]:mgraph_copy_2[i-1][j] = infmgraph_copy_2[j][i-1] = infpath,dis = Dijkstra(mgraph_copy_2,start,end,inf)path = passed[:-1]+pathfor k in range(len(passed)-1):dis += mgraph_copy_1[passed[k]-1][passed[k+1]-1]return path, disdef Init(mgraph,inf,start,end,k):  #初始化passed, noaccess, path, dis = [],[],[],[]PASS,DIS = [],[]path_,dis_ = Short_limit(mgraph, inf, start, end, passed, noaccess)PASS.append(path_)DIS.append(dis_)k = k-1for i in range(len(path_)-1):passed.append(path_[:i+1])noaccess.append([[path_[i],path_[i+1]]])for i in range(len(passed)):path_,dis_ = Short_limit(mgraph,inf,start,end,passed[i],noaccess[i])path.append(path_)dis.append(dis_)return passed, noaccess, path, dis, PASS, DIS, kdef Branch(passed, noaccess, path, dis, k, PASS, DIS):inx = dis.index(min(dis))PASS.append(path[inx])DIS.append(dis[inx])k = k-1for i in range(len(passed[inx]),len(path[inx])):passed.append(passed[inx]+path[inx][len(passed[inx]):i])noaccess.append(noaccess[inx]+[path[inx][i-1:i+1]])path_,dis_ = Short_limit(mgraph, inf, start, end, passed[-1], noaccess[-1])# if path_ == passed[-1][:-1]:if dis_ >= 999:del passed[-1]del noaccess[-1]else:path.append(path_)dis.append(dis_)del passed[inx]del noaccess[inx]del path[inx]del dis[inx]while k>0 and len(path) != 0:Branch(passed, noaccess, path, dis, k, PASS, DIS)return PASS, DISdef Yen(mgraph, inf, start, end, k):passed, noaccess, path, dis, PASS, DIS, k = Init(mgraph,inf,start,end,k)PASS, DIS = Branch(passed, noaccess, path, dis, k, PASS, DIS)print(f"共寻得{len(PASS)}最短路")for i in range(len(DIS)):print(f'第{i+1}短路,长{DIS[i]},{PASS[i]}')

测试

inf = 999 #此处表示极大值
mgraph = [[0,1,5,inf,inf,inf],[inf,0,3,1,6,inf],[6,2,0,4,2,inf],[inf,4,2,0,5,8],[inf,3,10,1,0,3],[inf,inf,inf,inf,inf,0]]
start,end,k = 1,6,15Yen(mgraph, inf, start, end, k)

输出

共寻得15最短路
第1短路,长9,[1, 2, 3, 5, 6]
第2短路,长9,[1, 2, 4, 3, 5, 6]
第3短路,长10,[1, 3, 5, 6]
第4短路,长10,[1, 2, 5, 6]
第5短路,长10,[1, 2, 4, 6]
第6短路,长10,[1, 2, 4, 5, 6]
第7短路,长15,[1, 2, 3, 5, 4, 6]
第8短路,长16,[1, 2, 3, 4, 6]
第9短路,长16,[1, 3, 2, 4, 6]
第10短路,长16,[1, 3, 5, 4, 6]
第11短路,长16,[1, 2, 5, 4, 6]
第12短路,长16,[1, 2, 3, 4, 5, 6]
第13短路,长16,[1, 3, 2, 5, 6]
第14短路,长16,[1, 3, 2, 4, 5, 6]
第15短路,长17,[1, 3, 4, 6]

3.优化方向

我的头快要裂开了，有没有懂得来帮看看，能不能把初始化函数Init()也整合到Branch()中，我这搞得好繁琐。

4.参考资源

[1] 史峰.组合优化理论与计算方法.
[2]【最短路–Dijkstra + Python】

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！