How would you find the shortest path from a collection of lists representing train lines?

So I have four “train lines” represented as lists:

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

Essentially, each letter serves as a “station”. If a station appears on multiple lines, you can transfer from one line to another, similar to many underground city transit systems. For example, the shortest path from “a” to “h” would be [“a”, “b”, “h”] because you can go from “a” to “b” in line1, transfer to line4, and then move from “b” to “h”.

I wish to find a simple way to find the shortest path given an origin and destination point. My current solution is to convert the lines into a graph by finding the neighboring stations of a station and pairing them with that station.

stations = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n"]
allLines = [line1, line2, line3, line4]
nodeGraph = {}
def getList(letter):
  neighbors = []
  for i in allLines:
     if letter in i:
        pos = i.index(letter)
        if pos == 0:
            neighbors.append(i[pos+1])
        elif pos == len(i) - 1:
            neighbors.append(i[pos-1])
        elif pos > 0 and pos < len(i) - 1:
            neighbors.append(i[pos-1])
            neighbors.append(i[pos+1])
  return neighbors

for station in stations:
   nodeGraph[station] = getList(station)

I then found a shortest path function on this website that outputs the shortest path from a graph input.

def SP(graph, start, end, path=[]):
  path = path + [start]
  if start == end:
      return path
  shortest = None
  for node in graph[start]:
      if node not in path:
          newpath = SP(graph, node, end, path)
          if newpath:
              if not shortest or len(newpath) < len(shortest):
                  shortest = newpath
  return shortest

I want to avoid the step of creating a graph altogether and derive the shortest path just from the four lists. Can someone help me out?

Answer

I implemented a heuristic and brutal-force algorithm to solve the problem with pure Python functions.

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}'")

The graph algorithms should certainly be favoured once the complexity of the problem increased….

P.S. My results are identical to the results from @Alain T.