python - Yen's K-shortest Algorithm Python Implementation - For a 10-node all-connected graph,我能达到的最大k低于我的预期

Question

我已经根据维基百科上的伪代码和 GitHub 上的一些开源代码(https://gist.github.com/ALenfant/5491853 和 https://github.com/Pent00/YenKSP)实现了 Yen 的 K 最短路径算法。我唯一不同的是，我没有完全移除 (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 之前，您需要遍历 A 中的路径并从图中删除大量边。

但是，在您的代码中，您从应该删除边的循环中调用 Dijkstra，因此您将只能在删除了一条边的图形上运行 Dijkstra，这限制了您可以找到的替代路线的数量。

尝试在调用 Dijkstra 的部分将缩进减少 2 个制表位。