Python 最短路径

Question

我有一个路线对象列表，其中保留了该路线的起点和终点：

class route:
    def __init__(self, start, end):
        self.start = start
        self.end = end

routeList = [
    route("Munich", "Cologne"),
    route("Berlin", "Hamburg"),
    ...
    ...
]

当用户输入他的起点和终点时，我想找到最短的路线组合。我不知道我怎么能让它工作。我看了一下 dijkstra 的算法，但它看起来只适用于点和距离，而不适用于路线。我只知道我必须递归地做，但我不知道怎么做。有什么想法吗？

编辑：例如用户可以输入：

"start: Munich"
"end: Berlin"

当然列表中一定有匹配的路由满足这个愿望（只是举例）

Answer 1

NetworkX 提供您正在寻找的功能。

您需要以构建合理图表的方式格式化您的数据（根据您的示例，我不完全确定您的所有数据是否都是成对的，或者是否有更多 "hops" "routes"), 然后你可以应用任何合理的寻路算法。

Answer 2

Dijkstra 会工作得很好。

每个城市都是图中的一个节点，两个城市之间的每条路线都是两个节点之间的边。一般来说，图的边可以有权重（或距离），但如果你不关心距离，只想要一条路径的 routes/edges 最少，你可以将每条边的权重设置为 1.

Python 最短路径

Python shortest path

python

routes

path