在有向图中，找到从s到t的最短路径，使得路径通过V的某个子集，让我们称它们为死亡节点 . 算法给出一个数n，当从s到t遍历时，该路径不能超过n个死亡节点 . 她找到最短路径的最佳方法是什么？我正在削弱Dijkstra，但是如何确保我们不会超过n个节点？请帮我调整Dijkstra's以包含这个条件 .
如果n很小，你可以制作n个图形副本，称它们为1到n级 .
从级别1的s开始 . 如果处于正常节点，则边缘会将您带到同一级别的节点 . 如果您处于死亡节点，则边缘会将您带到下一级别的节点 . 如果您在n级的死亡节点处，则边缘被省略 .
还将所有级别的t节点连接到新的单个目标T（零权重） .
然后计算从s到T的最短路径 .
这种方法的问题是图形大小上升了n倍，所以它只适用于小n .
另一种方法是增加每个边缘的权重，使变量x留下死亡节点 .
当您增加变量x时，最短路径将使用越来越少的死亡节点 . 调整x的值（例如，使用二分法），直到图形仅使用n个死亡节点 .
这应该采用最短路径的O（logn）评估 .
我将路上遇到的死节点数量添加为计算距离的新（稀疏）维度 - 基本上每个节点最多有n个最佳距离 .
实现自己的BFS将是类似的：除非路径上的总距离和死节点数都较小，否则您需要将“看到x死节点”看作与每个节点的“与死节点一起看”不同 .
p.s. ：如果您遇到这种方法，请发布代码到目前为止O :)
2 回答
小n
如果n很小，你可以制作n个图形副本，称它们为1到n级 .
从级别1的s开始 . 如果处于正常节点，则边缘会将您带到同一级别的节点 . 如果您处于死亡节点，则边缘会将您带到下一级别的节点 . 如果您在n级的死亡节点处，则边缘被省略 .
还将所有级别的t节点连接到新的单个目标T（零权重） .
然后计算从s到T的最短路径 .
这种方法的问题是图形大小上升了n倍，所以它只适用于小n .
大号
另一种方法是增加每个边缘的权重，使变量x留下死亡节点 .
当您增加变量x时，最短路径将使用越来越少的死亡节点 . 调整x的值（例如，使用二分法），直到图形仅使用n个死亡节点 .
这应该采用最短路径的O（logn）评估 .
我将路上遇到的死节点数量添加为计算距离的新（稀疏）维度 - 基本上每个节点最多有n个最佳距离 .
实现自己的BFS将是类似的：除非路径上的总距离和死节点数都较小，否则您需要将“看到x死节点”看作与每个节点的“与死节点一起看”不同 .
p.s. ：如果您遇到这种方法，请发布代码到目前为止O :)