python - 巴士路线 : obtaining multiple routes from only 2 stops per route

Question

所以我有一张公共(public)汽车可以乘坐的路线列表以及每条路线的距离:

routes = {'AB':5, 'BC':4, 'CD':8, 'DC':8, 'DE':6, 'AD':5, 'CE':2, 'EB':3, 'AE':7}

或者现在只是一个列表，因为距离现在还不重要:

paths = ['AB', 'BC', 'CD', 'DC', 'DE', 'AD', 'CE', 'EB', 'AE']

现在我正在尝试获取公共(public)汽车在给定起点和终点的情况下可能采用的路线列表，然后我想尝试合并最大停靠点数以限制数据输出。目前我有这个功能:

def route_variations(first_stop, last_stop, max_stops):
    possiblepaths = []

    for path in paths:
        x = path[0]     #first letter of each route
        if first_stop == x:
            possiblepaths.append(path)

    for path in paths:
        y = path[-1]    #last letter of each route
        if last_stop == y:
            possiblepaths.append(path)
    return possiblepaths

例如，如果我想从 C 开始和结束

route_variations('C','C', 10)

将返回以 C 开头并以 C 结尾的路线列表，即。 -> ['CD', 'CE', 'BC', 'DC']

所以现在我也需要连接路由。路线 C-E-B-C 需要我的输出中缺少的 E-B 路线。知道如何开始实现吗？然后加入他们实现像CDC这样的全路由而不是CD和DC？

Answer 1

正如对您问题的评论所暗示的那样，图论中有众所周知的算法来寻找路径。

但是，只是为了学习(说真的，只是为了学习，这段代码并不真正适合这个任务的一般情况)，我会尝试提供一个结构有点像你的简单例子代码，这样你就可以看到你在获取那些“连接路由”时遗漏了什么

基本原则是，当你找到一条正确的路径(通过比较第一个字母)时，你会寻找所有以这条路径开头的路径，通过再次调用函数，从自身内部(即递归)，第二个字母路径。:

paths = ['AB', 'BC', 'CD', 'DC', 'DE', 'AD', 'CE', 'EB', 'AE']


def route_variations(first_stop, last_stop, max_stops):
    possible_routes = []
    if max_stops == 0 or first_stop == last_stop:
        return possible_routes
    for path in paths:
        x,y = path
        if first_stop == x:
            if last_stop == y:
                possible_routes.append([path])
            routes_from_this_stop = route_variations(y, last_stop, max_stops - 1)
            possible_routes.extend([[path] + route for route in routes_from_this_stop])
    return possible_routes


print(route_variations('A', 'C', 10))

输出是:

[['AB', 'BC'], ['AD', 'DC'], ['AD', 'DE', 'EB', 'BC'], ['AE', 'EB', 'BC']]

注意:如果 route 有圆圈，您会看到许多类似的路线绕着圆圈(长度受 max_stops 限制)。

注意 2: 当 start 和 stop 相同时，这将不起作用，您将得到一个空结果，因此您的具体示例在这里不起作用 :(