你如何从一组代表火车线路的列表中找到最短路径？

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”]，因为你可以从第1行的“a”到“b”，转至第4行，然后从“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}'")

一旦问题的复杂性增加，图算法当然应该受到青睐....

P.S。我的结果与@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']

你如何从一组代表火车线路的列表中找到最短路径？

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

python

shortest-path