K最短路径Python不工作

Question

我对我的K最短路径算法有某些问题。该代码给出：

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 

这相当于https://en.wikipedia.org/wiki/K_shortest_path_routing它提供的伪码实现。该图给出为： 现在，它运行良好，如果我有起始节点S < 10和终止节点T < 10，但与S和T> 10，它返回一个空集，而它应该返回路径。请注意，我无法使用Networkx库。我只需要使用基本库在Python

此外，为了生成图表的代码是这样的：

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 

我运行它是这样的：

graph= create_dictionary(gen_p_graph(100,0.8)[1]) 
K_shortest_Paths(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

如果您致电K_shortest_Pathes(graph, "11", "10")，您将永远不会在集合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