如何从表示火车线路的列表集合中找到最短路径？

Question

因此，我将四条“火车线路”表示为列表：

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

从本质上讲，每个字母都是一个“站”。如果一个车站出现在多条线路上，您可以从一条线路换乘到另一条线路，这与许多地下城市交通系统类似。例如，从"a“到"h”的最短路径是"a“、"b”、"h“，因为您可以在line1中从"a”转到"b"，再转到line4，然后从"b“转到"h”。

我希望找到一种简单的方法来找到给定起点和终点的最短路径。我目前的解决方案是通过找到车站的相邻车站并将它们与该车站配对来将线转换为图形。

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)

然后，我找到了一个最短路径函数on this website，它可以从图形输入输出最短路径。

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

我想完全避免创建一个图的步骤，只从四个列表中推导出最短路径。有人能帮帮我吗？

Answer 1

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

一旦问题的复杂性增加，图算法肯定会受到青睐……

另外，我的结果和@Alain T的结果是一样的。

Answer 2

您可以使用广度优先方法，方法是构建一个路径列表，该列表将延伸一个桩号，直到到达目的地为止。通过先延长较短的路径，当您到达目的地时，您将确保在最短的路径上：

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']