辞書の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://gist.github.com/econchick/4666413