2017-12-27 217 views
-1

如何从字典中的关键字x到关键字y获得最快的可能方式,假定它们都是通过它们的数组值连接的。确定字典中从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连接到33连接做1, 8, 7, 6, 4 esc。

我已经做了一个函数,给你从x到y的跳转次数。我想要从x到y的键最短的数组。

例如,如果我挑2个值是远离对方喜欢:115 我想从1 -> 15获得的最短路径。这将是[1, 3, 8, 16, 15]

+1

这是Dijkstra算法。 – erip

+1

寻找广度优先的搜索实现 – DAle

回答