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

1.前言

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

2.代码实现

@Author: Michael 2022-09-16 21:57:27
This code is about Yen.



from Dijkstra import Dijkstra
import copy

def 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] = inf

    for i in passed:
        for j in range(len(mgraph)):
        #此步保证无重复点
            if i != passed[-1]:
                mgraph_copy_2[i-1][j] = inf
            mgraph_copy_2[j][i-1] = inf

    path,dis = Dijkstra(mgraph_copy_2,start,end,inf)

    path = passed[:-1]+path
    for k in range(len(passed)-1):
        dis += mgraph_copy_1[passed[k]-1][passed[k+1]-1]

    return path, dis

def 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-1

    for 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, k

def Branch(passed, noaccess, path, dis, k, PASS, DIS):
    inx = dis.index(min(dis))
    PASS.append(path[inx])
    DIS.append(dis[inx])
    k = k-1

    for 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, DIS

def 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,15

Yen(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]