Kは、最短経路のpython

Question

私はT.マイコードと呼ばれる先にSと呼ばれるソースからK最短経路を見つけることに問題を抱えている

は、次のようになります

K = 4 
S = 'C' 
T = 'A' 
B = {} 
P = set() 
count = {} 
for U in graph.keys(): 
    count[U] = 0 

B[S] = 0 
while(len(B)>=1 and count[T]<K): 
    PU = min(B, key = B.get) 
    cost = B[PU] 
    U = PU[len(PU)-1] 
    del B[PU] 
    count[U] += 1 
    if U==T: 
     P.add(U) 
     if count[U]<=K: 
      V = graph[U].keys() 
      for v in V: 
      if v not in PU: 
       PV = PU+v 
       B[PV] = cost+1 

これは、擬似の実際のコードと同等に相当しますコードはhttps://en.wikipedia.org/wiki/K_shortest_path_routingにあります。 4つのパスが存在すべきであるのに対して私の出力は、この

{'A'} 

のように見えます

{

'A': {'C': 4.0, 'B': 10.0, 'E': 10.0, 'D': 10.0, 'G': 1.0, 'F': 2.0, 'I': 3.0, 'H': 3.0, 'J': 10.0}, 'C': {'A': 4.0, 'B': 5.0, 'E': 9.0, 'D': 6.0, 'G': 9.0, 'F': 10.0, 'I': 5.0, 'H': 10.0, 'J': 5.0}, 'B': {'A': 2.0, 'C': 10.0, 'E': 8.0, 'D': 1.0, 'G': 8.0, 'F': 4.0, 'I': 2.0, 'H': 2.0, 'J': 6.0}, 'E': {'A': 9.0, 'C': 5.0, 'B': 10.0, 'D': 4.0, 'G': 9.0, 'F': 9.0, 'I': 3.0, 'H': 3.0, 'J': 7.0}, 'D': {'A': 4.0, 'C': 6.0, 'B': 5.0, 'E': 7.0, 'G': 1.0, 'F': 1.0, 'I': 2.0, 'H': 9.0, 'J': 3.0}, 
'G': {'A': 2.0, 'C': 10.0, 'B': 3.0, 'E': 1.0, 'D': 10.0, 'F': 5.0, 'I': 5.0, 'H': 6.0, 'J': 1.0}, 'F': {'A': 2.0, 'C': 3.0, 'B': 6.0, 'E': 7.0, 'D': 8.0, 'G': 10.0, 'I': 1.0, 'H': 8.0, 'J': 2.0}, 'I': {'A': 1.0, 'C': 1.0, 'B': 2.0, 'E': 1.0, 'D': 6.0, 'G': 7.0, 'F': 1.0, 'H': 6.0, 'J': 2.0}, 
'H': {'A': 3.0, 'C': 4.0, 'B': 5.0, 'E': 1.0, 'D': 2.0, 'G': 6.0, 'F': 4.0, 'I': 1.0, 'J': 4.0}, 
'J': {'A': 5.0, 'C': 6.0, 'B': 1.0, 'E': 8.0, 'D': 7.0, 'G': 9.0, 'F': 8.0, 'I': 10.0, 'H': 1.0}} 

：実際の変数は私のグラフは次のようになり、また、疑似Code.Furthermoreと同じです。

また、NetworkxまたはGraphライブラリを使用することはできません。私はPythonでのみ基本的なライブラリを使用する必要があります。

誰かが問題を理解できますか？

Answer 1

コードを少し変更しました。ノードがターゲットであり、それに続くコードであることを確認する場所にエラーがありました。

K = 4 
S = 'C' 
T = 'F' 
B = {} 
P = set() 
count = {} 
for U in graph.keys(): 
    count[U] = 0 

B[S] = 0 
while(len(B)>=1 and count[T]<K): 
    PU = min(B, key = B.get) 
    print('Minimum Distance found in this loop : ' , PU) 
    cost = B[PU] 
    U = PU[len(PU)-1] 
    del B[PU] 
    count[U] += 1 
    if(U == T): 
     P.add(PU) 
     print('Closest neighbour of ' , S , ' is : ', U) 
     print('Reached target') 
     print('Final map : ', P) 
     exit(0) 
    else: 
     if count[U] <= K: 
      V = graph[U].keys() 
      print('Looking at neighbours of : ', PU) 
      for v in V: 
      if v not in PU: 
       PV = PU + v 
       print(PV) 
       B[PV] = cost+1 
      print('B dictionary is : ', B) 

を実行し、このプログラムを、あなたは次のようなものを取得します：出力はかなり自己記述する必要があります

Minimum Distance found in this loop : C 
Looking at neighbours of : C 
CA 
CB 
CE 
CD 
CG 
CF 
CI 
CH 
CJ 
B dictionary is : {'CA': 1, 'CB': 1, 'CE': 1, 'CD': 1, 'CG': 1, 'CF': 1, 'CI': 1, 'CH': 1, 'CJ': 1} 
Minimum Distance found in this loop : CA 
Closest neighbour of C is : A 
Reached target 
Final map : {'CA'} 

。 また、各ノードにウェイトが関連付けられているとします（それはそれと推測します）。次に、距離のカウントをそれぞれの対応するネイバーに1だけインクリメントする理由がわかりません。

Answer 2

問題1： if count[U]<=K:をwhileループの外に出す。

問題2：これを変更 ：これまで

if U==T: 
    P.add(U) 

：

if U==T: 
    P.add(PU) 

問題3：私はこれについて少し混乱しています。 変更するPU = min(B, key = B.get)これはPU = min(B,key=lambda x:B[x])

それは私のために働いたので、追加の問題に遭遇すれば教えてください。