使用 Dijkstra 或 Bellman Ford 算法修改最短路径
我们如何使用 Dijkstra 或 Bellman–Ford 算法来找到图中的最短路径，如果我们去特定的顶点，该图中的一些边会受到影响。这样，受影响的边的长度将大于或小于原始长度。
How can we use Dijkstra's or Bellman–Ford's algorithm to find shortest path in a graph whose some of edges are affected if we go specific vertices. Such that, the affected edge's length will be more than or less than the original length.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果我理解正确的话，您希望根据当前路径中访问的节点来更改图中边的成本。评论中的一个例子是：
“边AB的长度为3，但如果你也访问节点C，AB的长度将为5”
现在，似乎没有办法使用像Djikstra算法这样的算法，因为有该算法中的贪婪步骤在每个阶段选择“最佳”节点。该点的“最佳”节点可能会在以后发生变化（由于上述规则）的概念违反了贪婪方法的概念，该方法假设我们按照从最佳成本到最差成本的顺序有效地访问节点。我不确定这是否像建议的那样是 NP 难的，但它肯定不能从一开始就使用 Dijikstra 类型的方法。不过对于这个问题+1。
If I understand this right, you want to change the cost of an edge in a graph depending on nodes which are visited in your current path. An example from the comments is:
"Edge AB has length 3, but if you also visit node C, AB's length will be 5"
Now, there doesn't seem to be a way for something like Djikstra's algorithm to be used as there is a greedy step in that algorithm which picks the 'best' node at every stage. The notion that the 'best' node at that point may change at a later time (due to a rule such as above) violates the concept of the greedy approach which assumes that we are effectively visiting nodes in order from best to worst cost. I'm not certain if this is NP hard as suggested but it certainly cannot use a Dijikstra kind of approach from the start. +1 for the problem though.