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，它 return 是一个空集，而它应该 return 路径.请注意，我不能使用 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')

return 一个空集，而它应该 return 路径。

Answer 1

如果您调用 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

Answer 2

我认为您正在努力实现的目标。试试这个。

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

K 最短路径 Python 不工作

K Shortest Path Python Not Working

python

algorithm

shortest-path