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

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)

这是我想要得到的结果： station1-->station2-->station3-->station4-->station5-->station6-->station7-->station8-->station9-->station10-->station11-->station12

编辑： Canh的答案：

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"

一些路由示例应该是：

station12 --> station11 --> station10 --> station9 --> station1

station12 --> station11 --> station10 --> station9 --> station2 --> station1

station12 --> station11 --> station10 --> station8 --> station7 --> station6 --> station5 --> station4 --> station3 --> station2 --> station1

如果 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)

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

Algorithm to find the path (train path with interchanges)

python

python-3.x

path-finding