对于我的学士论文，我遇到了以下问题(解决它可能对论文的实际问题有用)。我有一个加权有向图 G，顶点 V 和来自 V 的两个顶点，开始 s 和目标 t。我最多可以删除 k 个顶点。我需要找到顶点，删除这些顶点将使调整后的图中从 s 到 t 的最短路径的成本(长度)最大化。
我想，这个问题应该在之前的文献中得到解决，但是我没有找到相关的文章。如果能提供相关文献的任何链接，我将不胜感激。
最佳答案
可以申请Yen's Algorithm找到最短的 K 路径。现在你如何在你的代码中应用它？您申请的不是前 K 条路径，而是所有与最短路径长度相同的路径。一旦找到所有这些(以 K1 为计数)，您现在采用每条路径并删除(模拟您删除)一个顶点(如果您已经考虑过可以跳过它)但如果没有，现在您遇到最短路径的问题具有可跳过顶点的图。在每一步，您都尝试最大化“最短路径”并选择该顶点。我正在考虑一种更优化的方法，但这是我能想到的最好的方法。
你做了 K 次:
- Yen 的算法是否按照我所说的进行了修改。
- 找到移除一个顶点以增加最小距离的最佳局部解决方案。
关于algorithm - 最长最短路径(不完全是)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42492378/