日元的K最短算法Python的實現 - 對於10節點全連接圖，我可以達到的最大k低於我的預期

Question

我已經實現了基於維基百科上的僞代碼的Yen的K-最短路徑算法， GitHub上的幾個開源代碼（https://gist.github.com/ALenfant/5491853和https://github.com/Pent00/YenKSP）。我做的唯一不同的事情就是完全去除（i，i + 1）邊緣，我將邊緣的長度改爲無窮大（這相當於刪除我猜測的本質邊緣）

我測試了我的具有10節點圖的代碼，其中所有節點彼此連接。我預計我可以生成的無循環路由的最大數量超過10萬，但事實證明，我的代碼只能找到最短的第9條路由。這是日元的限制嗎？

以下是我的代碼和10節點樣本數據。

def yen(nodes, distances, start, end, max_k): 
# Dictionary "solspace" stores actual k-shortest paths, the first of which comes from Dijkstra's algorithm. 
solspace = {} 
potentialsolspace = [] 
selected = [] 
# Adding the Dijkstra's shortest path into solspace dictionary 
solspace[0] = (dijkstra(nodes, distances, start, end))[0] 
# max_k is the specified number of shortest paths you want to find 
max_k = max_k 

# Looping from k = 1 to k = max_K and the 0 to (size of previous entry of solspace)-1 
# Reference: http://en.wikipedia.org/wiki/Yen's_algorithm 

for k in range(1, max_k): 
    #distances = copy.deepcopy(actual_distances) 
    for i in range(0, (len(solspace[k - 1]) - 1)): 
     spur_node = solspace[k - 1][i] 
     spur_node_plus_one = solspace[k - 1][i + 1] 
     root_path = solspace[k - 1][0:i + 1] 

     for shortPath in solspace: 

      path_root_path = (solspace[shortPath])[0:i + 1] 
      #print(path_root_path) 
      if root_path == path_root_path and (len(solspace[shortPath]) - 1 > i): 
       # make each overlapping edges of root path and path_root_path infinity, hence impossible to select 
       distances[spur_node][spur_node_plus_one] = float('inf') 
       distances[spur_node_plus_one][spur_node] = float('inf') 

       # Call Dijkstra function to compute spur path (the shortest path between spur node 
       # and end ignoring the i,i+1 edge 
       spur_path_a = dijkstra(nodes, distances, spur_node, end) 
       spur_path = spur_path_a[0] 
       # Restore actual dist to distances nested dictionary 
       # Total path is just the combination of root path & spur path 
       total_path_tempo = root_path + spur_path 
       total_path = [] 
       # This removes duplicates nodes but note that this is O(n^2) computing time, not efficient 
       # Ref: Stack Overflow questions:480214 
       [total_path.append(item) for item in total_path_tempo if item not in total_path] 
       print(total_path) 
       # build up potentialsolspace by adding in total path which are yet found in solspace or Potential 
       # hence, the use of nested if 
       if total_path not in solspace.values(): 
        if [total_path, cost_path(total_path, distances)] not in potentialsolspace[:]: 
         potentialsolspace.append([total_path, cost_path(total_path, distances)]) 

       distances = copy.deepcopy(actual_distances) 
    # This handles the case of there being no spur paths, or no spur paths left. 
    # This could happen if the spur paths have already been exhausted (added to A), 
    # or there are no spur paths at all such as when both the source and sink vertices lie along a "dead end". 
    if len(potentialsolspace) is 0: 
     break 
    wcg = min(potentialsolspace, key=lambda x: x[1]) 
    # remove selected potential shortest path from the potential solspace 
    potentialsolspace.remove(wcg) 
    # Attach minimum of potentialSolSpace into solspace dictionary 
    solspace[k] = wcg[0] 

return solspace 

以下是以Python嵌套的不連續格式排列的10節點示例。主鍵是起源，而輔助鍵是主鍵的鄰居。值等於主鍵和輔助鍵之間的距離。

{'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}} 

Answer 1

我認爲這個問題是在這個部分：

 for shortPath in solspace: 
      path_root_path = (solspace[shortPath])[0:i + 1] 
      #print(path_root_path) 
      if root_path == path_root_path and (len(solspace[shortPath]) - 1 > i): 
       # make each overlapping edges of root path and path_root_path infinity, hence impossible to select 
       distances[spur_node][spur_node_plus_one] = float('inf') 
       distances[spur_node_plus_one][spur_node] = float('inf') 

       # Call Dijkstra function to compute spur path (the shortest path between spur node 
       # and end ignoring the i,i+1 edge 
       spur_path_a = dijkstra(nodes, distances, spur_node, end) 

與此相比，維基百科：

  for each path p in A: 
       if rootPath == p.nodes(0, i): 
        // Remove the links that are part of the previous shortest paths which share the same root path. 
        remove p.edge(i, i + 1) from Graph; 

      for each node rootPathNode in rootPath except spurNode: 
       remove rootPathNode from Graph; 

      // Calculate the spur path from the spur node to the sink. 
      spurPath = Dijkstra(Graph, spurNode, sink); 

你超過在一個路徑意味着環路和刪除大量的邊緣運行Dijkstra之前的圖形。

但是，在您的代碼中，您應該從循環內部調用Dijkstra以消除邊緣，因此您只會在圖形上運行Dijkstra並刪除單邊，這會限制您可以找到的替代路徑的數量。

嘗試在調用Dijkstra的部分減少2個製表符。