Как найти кратчайший путь из набора списков, представляющих железнодорожные линии?

Я реализовал эвристический алгоритм грубой силы для решения проблемы с чистыми функциями Python.

from itertools import combinations, permutations

stations = [
    "a", "b", "c", "d", "e",
    "f", "g", "h", "i", "j",
    "k", "l", "m", "n"
]

line1 = ["a", "b", "f", "d", "e"]
line2 = ["c", "e", "j", "g", "i"]
line3 = ["c", "j", "k", "l", "m"]
line4 = ["h", "b", "e", "a", "n"]
lines = [line1, line2, line3, line4]


def validate_step(x, y, lines):
    """
    check if we can change fron x to y in a single line
    """
    for i, line in enumerate(lines):
        if (x in line) and (y in line):
            if abs(line.index(x) - line.index(y)) == 1:
                return True, (i, (line.index(x), line.index(y)))
    else:
        return False, None


def find_shortest(x, y, lines, max_step=12):
    # check if x and y are in the same line
    valid = validate_step(x, y, lines)
    if valid[0]:
        return 0, [valid[1]]
    # iterating over all the possibilities
    possible_inter = [s for s in stations if s not in (x, y)]
    for im_step in range(1, max_step):  # intermediate step
        inter_steps = combinations(possible_inter, im_step)
        for i_step in inter_steps:
            for steps in permutations(i_step):
                solution = []
                is_path_valid = True
                full_path = [x] + list(steps) + [y]
                
                for p1, p2 in zip(full_path[:-1], full_path[1:]):
                    valid = validate_step(p1, p2, lines)
                    is_path_valid *= valid[0]
                    solution.append(valid[1])

                if is_path_valid:
                    return im_step, solution
    print("Did not find a solution")
    return None, None


x = "d"
y = "n"

result = find_shortest(x, y, lines)

print(f"with {result[0]} changes, the path from '{x}' to '{y}' is find")
for step in result[1]:
    s1 = lines[step[0]][step[1][0]]
    s2 = lines[step[0]][step[1][1]]
    print(f"- Taking line {step[0]+1}, go from '{s1}' to '{s2}'")

Безусловно, следует отдавать предпочтение графовым алгоритмам, когда сложность проблемы возрастает ....

P.S. Мои результаты идентичны результатам @Alain T.

Вы можете использовать подход «сначала в ширину», создав список путей, которые вы продолжите на одну станцию, пока не достигнете пункта назначения. Если сначала продлить более короткие пути, вы гарантированно окажетесь на одном из кратчайших путей, когда достигнете пункта назначения:

def shortPath(origin,destination,*lines):
    paths    = [[origin]]        # start from origin
    visited  = set()             # only extend once per station
    while paths:                 # until no more extensions
        path = paths.pop(0)                   # shortest paths first
        if path[-1]==destination: return path # arrived!
        for line in lines:                    # find a transfer 
            if path[-1] not in line:continue  # no transfer on line
            i = line.index(path[-1])          # from station's location
            for station in line[i-1:i]+line[i+1:i+2]: # previous/next stations
                if station in visited : continue # already been there
                paths.append(path + [station])   # add longer path
                visited.add(station)
    return [] # no path to destination

выход:

line1 = ["a", "b", "f", "d", "e"]
line2 = ["c", "e", "j", "g", "i"]
line3 = ["c", "j", "k", "l", "m"]
line4 = ["h", "b", "e", "a", "n"]

print(shortPath("a","h",line1,line2,line3,line4))
# ['a', 'b', 'h']

print(shortPath("d","n",line1,line2,line3,line4))
# ['d', 'e', 'a', 'n']

print(shortPath("h","m",line1,line2,line3,line4))
# ['h', 'b', 'e', 'j', 'k', 'l', 'm']