最长最短路径（不完全）

Question

对于我的学士论文，我遇到了以下问题（解决这个问题可能对论文的实际问题有用）。我有一个加权有向图G顶点V和V两个顶点，开始s和目的地t。我可以删除至多k顶点。我需要找到顶点，删除顶点将使调整图中从s到t的最短路径的成本（长度）最大化。

我想，这个问题本来应该在文献中讨论过，但是，我没有设法找到相关的文章。我会很感激有关文献的任何链接。

Answer 1

您可以申请Yen's Algorithm找到最短的K路径。现在你如何在你的代码中应用它？您不适用于第一个K路径，而是适用于所有与最短路径长度相同的路径。一旦你找到所有这些（K1作为一个计数），你现在采取每个路径并删除（模拟你删除）一个顶点（如果你已经认为你可以跳过它），但如果没有，现在你有一个问题最短路径带有可跳过顶点的图形。在每一步中，您都尝试最大化“最短路径”并选择该顶点。我正在考虑一种更优化的方式，但这是我从头到尾所能做到的最好的方式。

你做K次：正如我所说的修改

1. 待办事项日元的算法。
2. 找到删除一个顶点以增加最小距离的最佳局部解决方案。