查找路径的算法（带立交桥的列车路径）

Question

这是我用python编写的简化代码，我试图用递归来找出用户想要从station1到station12需要去哪些站点（作为一个例子），但是我根本搞不清楚，请大家帮我，我已经坚持了这么久了，非常感谢

x = ["station1","station2","station3","station4"]
y = ["station5","station6","station7","station8"]
z = ["station9", "station10"]
e = ["station11", "station12"]
array = x, y, z, e
interchange = [ ["station4", "station5"] , ["station8", "station9"], ["station10, station[11] ]
cur = "station1"
des = "station12"

所以下面的代码是我试图找到的算法，但根本不起作用

def find(cur, des):
    check = 0
    for each in array:
        if cur in each and des in each:
            check = 1
            ind = each.index(cur)
            ind2 = each.index(des)
            for i in range(ind, ind2+1):
                print("-->", end = " ")
                print(each[i], end = " ")
            print("\n")
    for each in array:
        if cur in each and check == 0:
            for station in interchange:
                if station in each and cur != station:
                    ind = each.index(cur)
                    ind2 = each.index(station)
                    for i in range(ind, ind2+1):
                        print("-->", end = " ")
                        print(each[i], end = " ")
                    print("\n")
                    find(station, des)

这就是我想要得到的结果： 站1-->；站点2-->；站点3-->；站点4-->；站点5-->；站点6-->；站点7-->；站点8-->；站点9-->；站点10-->；车站11-->；车站12

编辑： 答案是：

def find(cur, des):
    check = 0
    for each in array:
        if cur in each and des in each:
            check = 1
            ind = each.index(cur)
            ind2 = each.index(des)
            for i in range(ind, ind2+1):
                print("-->", end = " ")
                print(each[i], end = " ")
            print("\n")
    for each in array:
        if cur in each and check == 0:
            for station1, station2 in interchange:
                if station1 in each and cur != station1:
                    ind = each.index(cur)
                    ind2 = each.index(station1)
                    for i in range(ind, ind2+1):
                        print("-->", end = " ")
                        print(each[i], end = " ")
                    find(station2, des)

对不起，我还有一个问题，如果条件是：

x = ["station1","station2","station3","station4"]
y = ["station8","station7","station6","station5"]
z = ["station9", "station10"]
e = ["station11", "station12"]

interchange = [ ["station1", "station9"], ["station5", "station4"] , ["station9", "station8"], ["station10", "station11" ],  ["station2", "station9" ] ]

cur = "station12"
des = "station1"

一些路线示例应为：

站点12-->；车站11-->；站点10-->；站点9-->；车站1

站点12-->；车站11-->；站点10-->；站点9-->；站点2-->；车站1

站点12-->；车站11-->；站点10-->；站点8-->；站点7-->；站点6-->；站点5-->；站点4-->；站点3-->；站点2-->；车站1

如果cur和des被交换：

cur = "station1"
des = "station12"

那么可能的路线就和前一条相反了

Answer 1

您的interchange变量是一个列表的列表。在语句for station in interchange中，station是一个列表，因此条件station in each永远不会为真

我想应该是这样

for station1, station2 in interchange:
    if station1 in each and cur != station1:
        ind = each.index(cur)
        ind2 = each.index(station1)
        for i in range(ind, ind2+1):
            print(" >", end = " ")
            print(each[i], end = " ")
        print("\n")
        find(station2, des)