改进的最短路径算法：使用Dijkstra或Bellman-Ford算法

Question

改进的最短路径算法：使用Dijkstra或Bellman-Ford算法

c++algorithmshortest-pathdijkstrabellman-ford

3

如何使用Dijkstra或Bellman-Ford算法在一个图中查找最短路径，其中一些边受到特定顶点影响。这样，受影响的边的长度将大于或小于原始长度。

- Alaattin KAYRAK

1

根据您提供的信息，很难做出任何陈述。边缘是否会在任何时候变为负数？仅当访问任一端点时，边缘成本才会被修改，还是通过访问第三个节点也可以进行修改？还有其他保证吗？ - David Rodríguez - dribeas

你能提供一个受影响的图的例子吗？比如，边AB的长度为3，但如果你还要访问节点C，那么AB的长度将变为5。这是你的意思吗？ - Nikita Rybak

@Alock，不同的“访问”如何影响单个边缘？比如，你访问了C和D，C说|AB|=5，D说|AB|=7。 - Nikita Rybak

@Nikita Rybak，与此同时，我忘了告诉你C和D不能同时在路径中；很抱歉。影响同一节点的节点不能在同一路径中。因此，只有C或D的效果是有效的。但是存在许多元组，不仅仅是C和D。 - Alaattin KAYRAK

还有其他未说明的限制吗？特别是对于包含更改与其他边缘不同值的节点的路径。我猜解决问题的更高级别描述可以帮助提供可能的解决方案。此外，考虑重新定义相同的问题，其中边缘由于可能将边缘分成两个单独的值而被固定，并在最后验证每个路径中的每个值...但我不确定这是否会让您接近解决方案。看起来是一个足够难的问题（NP完全？） - David Rodríguez - dribeas

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kyun · Accepted Answer

如果我理解正确，您想根据当前路径中访问的节点更改图中边缘的成本。评论中的一个示例是：

"边AB的长度为3，但如果您还访问节点C，则AB的长度将为5"

现在，似乎没有办法使用像Djikstra算法这样的东西，因为该算法中有一个贪婪步骤，在每个阶段选择“最佳”节点。在后面的时间点上，“最佳”节点可能会发生变化（由于上述规则等），这违反了贪婪方法的概念，该方法假定我们有效地按照从最好到最差成本的顺序访问节点。我不确定这是否像建议的那样是NP难的，但它肯定不能从一开始就使用Dijikstra类型的方法。对于这个问题加1。