Yen 的第三条（和）后续最短路径算法（k-最短路径问题）

Question

所以我了解 Yen 的算法如何适用于第二短的迭代，但不适用于任何后续迭代。在第三次迭代中，您是否一次删除一对唯一的边（一条来自第二条第二最短路径，一条来自第一条最短路径）？

    'MCO': {'ATL': 1.02, 'MIA': 0.63},
    'ATL': {'MCO': 1.07, 'DFW': 1.87},
    'DFW': {'MIA': 2.65, 'ATL': 1.63, 'DEN': 1.60},
    'DEN': {'LAS': 1.42, 'ORD': 2.08, 'DFW': 1.47},
    'LAS': {'DEN': 1.50, 'LAX': 0.71},
    'LAX': {'JFK': 5.43, 'ORD': 3.83, 'LAS': 0.75,},
    'ORD': {'CLT': 1.40, 'JFK': 1.67, 'LAX': 3.50},
    'MIA': {'DFW': 2.65, 'MCO': 0.67, 'JFK': 2.38},
    'CLT': {'ORD': 1.57,},
    'JFK': {'MIA': 2.53, 'ORD': 2.00, 'LAX': 4.85},

找到第一条最短路径：MIA -> DFW -> DEN -> LAS

找到第二条最短路径：MIA -> MCO -> ATL -> DFW -> DEN -> LAS

现在，对于第三次迭代，如果我仅删除 MIA -> MCO 或 MCO -> ATL 或 ATL -> DFW ，将再次找到第一条最短路径。这是否意味着我必须在每对独特的边上运行 Dijkstra 算法，即 15 次？

Answer 1

将再次找到第一条最短路径。

由于您忘记发布代码，我们只能猜测您的错误所在。

我最好的猜测是您未能正确实现伪代码行

        if (totalPath not in B):
            B.append(totalPath);

B 是潜在最短路径的集合（你不喜欢那些使用无意义变量名的人吗？）。 if 语句防止存储已“再次找到”的路径