确定字典中从 x 键到 y 键的最快路线？

Question

假设所有键都通过它们的数组值连接，如何以最快的方式从字典中的键 x 到键 y。

network={
 1: [3],
 2: [4],
 3: [1, 8, 7, 6, 4],
 4: [2, 3, 6, 5],
 5: [4, 11, 10],
 6: [3, 11, 4],
 7: [3, 8, 11],
 8: [3, 16, 9, 7],
 9: [8, 16, 14, 11],
 10: [5, 11, 13],
 11: [5, 6, 7, 9, 14, 10],
 12: [13],
 13: [10, 14, 12],
 14: [9, 16, 13, 11],
 15: [16],
 16: [8, 15, 14, 9]}

键代表值x或y。以及它们的阵列，它们相互连接的方式。示例：1 连接到 3，3 连接到 1, 8, 7, 6, 4 esc。

我制作了一个函数，可以为您提供从 x 到 y 的跳跃次数。

def jumps(x, y, network):
x={x}
for i in range(1, len(network)):
    x=neighbors(x, network)
    if(y in x):
        return i

def neighbors(x, network):
seen=[]
for krizisce in x:
    for izvoz in network[krizisce]:
        if izvoz not in doslej and izvoz not in seen:
            seen.append(izvoz)
return {x for x in seen}

但我想获得从 x 到 y 的最短键数组。

例如，如果我选择 2 个彼此相距很远的值，例如：1 和 15 我想从 1 -> 15 获得最短路径。那将是 [1, 3, 8, 16, 15]

Answer 1

这是寻找最短路径的标准案例，在整个互联网上都有实现。

想了解的可以看这里：https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

如果您需要快速实现，这似乎与您的实现非常相似：https://gist.github.com/econchick/4666413

确定字典中从 x 键到 y 键的最快路线？

Determining the fastest route from x key to y key in dictionary?

python

dictionary

shortest-path