K Kürzester Pfad Python funktioniert nicht

Question

Ich habe bestimmte Probleme mit meinem K Shortest Path-Algorithmus. Der Code wird wie gegeben:

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 

Dieses zu https://en.wikipedia.org/wiki/K_shortest_path_routing entsprechen, die den Pseudo-Code für die Implementierung zur Verfügung stellt. Der Graph wird wie gegeben: Nun Es funktioniert gut, wenn ich Startknoten S < 10 und Endknoten T < 10, aber mit S und T> 10, es gibt einen leeren Satz, während er den Pfad zurückkehren sollte. Bitte beachten Sie, dass ich keine Networkx-Bibliotheken verwenden kann. Ich habe nur grundlegende Bibliotheken in Python

Außerdem verwenden müssen, das Codediagramm zu generieren, ist dies:

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 

Und ich laufe es wie folgt aus:

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

Rückkehr eine leere Menge, während es sollte Pfade zurückgeben.

Answer 1

Was ich vermute, versuchen Sie zu erreichen. Versuche dies.

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

Wenn Sie rufen K_shortest_Pathes(graph, "11", "10") Sie nie P ein Element zu dem Satz hinzuzufügen. Lies meine Inline-Kommentare.

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