K最短パスPythonは私が私のK最短経路アルゴリズムで特定の問題を抱えている

Question

動作していません。これは、実装のための擬似コードを提供https://en.wikipedia.org/wiki/K_shortest_path_routingに相当する

def K_shortest_Paths(graph,S,T,K=4): 
    '''Initialize Variables Accordingly''' 
    B = {} 
    P = set() 
    count = {} 
    for U in graph.keys(): 
     count[U] = 0 
    B[S] = 0 
    '''Algorithm Starts''' 
    while(len(B)>=1 and count[T]<K): 
     PU = min(B,key=lambda x:B[x]) 
     cost = B[PU] 
     U = PU[len(PU)-1] 
     del B[PU] 
     count[U] += 1 
     if U==T: 
      P.add(PU) 
     if count[U]<=K: 
      V = graph[U].keys() 
      for v in V: 
       if v not in PU: 
        PV = PU+v 
        B[PV] = cost+1   
    return P 

：コードは次のように与えられます。 は今、それは私が< 10ノードS、および終端ノードT < 10を起動しているだけでなく場合は動作しますが、SおよびT> 10で、それがパスを返さなければならないのに対し、空のセットを返します。グラフが与えられます。私はNetworkxライブラリを使用できないことに注意してください。

def create_dictionary(graph): 
    D = {} 
    for item in graph.items(): 
     temp = {} 
     connected = list(item[1]) 
     key = item[0] 
     for V in connected: 
      temp[str(V)] = 1 
     D[str(key)] = temp 
    return D 

def gen_p_graph(nodes,prob): 
    if prob>1: 
     er='error' 
     return er 
    graph_matrix=np.zeros([nodes,nodes]) 
    num_of_connections=int(((nodes * (nodes-1)) * prob )/2) 
    num_list_row=list(range(nodes-1)) 
    while(np.sum(np.triu(graph_matrix))!=num_of_connections): 
      row_num=random.choice(num_list_row) 
      num_list_col=(list(range(row_num+1,nodes))) 
      col_num=random.choice(num_list_col) 
      if graph_matrix[row_num,col_num]==0: 
       graph_matrix[row_num,col_num]=1 
       graph_matrix[col_num,row_num]=1 

    #create dictionary 
    df=pd.DataFrame(np.argwhere(graph_matrix==1)) 
    arr=np.unique(df.iloc[:,0]) 
    dct={} 
    for i in range(graph_matrix.shape[0]): 
     dct[str(i)]=set() 
    for val in arr: 
     dct[str(val)].update(df.loc[df.iloc[:,0]==val].iloc[:,1].values) 

    return pd.DataFrame(graph_matrix),dct 

そして、私はこのようにそれを実行します：私は

さらにPythonでの基本的なライブラリを使用する必要があり、グラフを生成するためのコードはこれです

graph= create_dictionary(gen_p_graph(100,0.8)[1]) 
K_shortest_Paths(graph,'11','10') 

リターンそれに対し、空のセットをパスを返す必要があります。あなたがK_shortest_Pathes(graph, "11", "10")を呼び出す場合

Answer 1

あなたが達成しようとしているものは何ですか？これを試して。

def k_shortest_paths(graph, src_node, dest_node, k=4): 
    result = [] 
    pathes = [[src_node]] 
    while len(pathes) > 0 and len(result) < k: 
    path = pathes.pop() 
    last_node = path[-1] 
    if last_node == dest_node: 
     result.append(path) 
    else: 
     for child_node in graph[last_node].keys(): 
     if child_node not in path: 
      pathes.append(path + [child_node]) 
    return result 

Answer 2

あなたはセットPに要素を追加することはありません。私のインラインコメントを読んでください。

def K_shortest_Paths(graph,S,T,K=4): 
    '''Initialize Variables Accordingly''' 
    B = {} 
    P = set() 
    count = {} 
    for U in graph.keys(): 
     count[U] = 0 

    # currently the B has only one item, i.e. { S: 0 } => { "11": 0 } 
    B[S] = 0 

    '''Algorithm Starts''' 
    while(len(B)>=1 and count[T]<K): 

     # results in the only key in B, i.e. PU = S => PU = "11" 
     PU = min(B,key=lambda x:B[x]) 

     cost = B[PU] 

     # U = PU[len(PU) - 1], where PU = "11" => 
     # U = "11"[len("11")-1] => 
     # *** U = "1" 
     U = PU[len(PU)-1] 

     del B[PU] 
     count[U] += 1 

     # *** U == T => "1" == T => "1" == "10" which is False 
     # Thus nothing is ever added to set P 
     if U==T: 
      P.add(PU) 

     if count[U]<=K: 
      V = graph[U].keys() 
      for v in V: 
       if v not in PU: 
        PV = PU+v 
        B[PV] = cost+1   
    return P