查找具有parent对象的两个顶点之间的最短路径

Question

我试图实现一个函数，使用给定的父对象打印源和目标顶点之间的最短路径。函数应该返回一个使用"→";连接相邻的顶点(参见预期的输出)。我该怎么做呢?

def get_path(parents, source, target):
path = ''
### START YOUR CODE ###
pass
### END YOUR CODE ###
return path
# Do not change the test code here
path = get_path(parents, 's', 'z')
print(path)

我的期望输出是:年代→y→x→t→z

这就是我目前所做的，但是它没有得到我期望的输出。

def get_path(parents, source, target):
path = [target]
### START YOUR CODE ###
while True:
key = parents[path[0]]
path.insert(0, key)
if key == source:
break
### END YOUR CODE ###
return path

我:[‘s’,‘y’,‘x’,‘t’,' z ']

Answer 1

您所需要做的就是使用.join()方法将列表转换为适当的字符串。

首先指定分隔符:

" -> "

然后，我们可以使用分隔符连接列表中的字符串:

" -> ".join(['s', 'y', 'x', 't', 'z'])

在这一点我们得到所需的输出:

s -> y -> x -> t -> z