从一个来源经过N个边缘的最短路径？ [英] Shortest path from one source which goes through N edges ?
问题描述
在我的经济学研究中，我目前正在处理一个特定的最短路径问题：
给定一个有边缘权重的定向确定性动态图，我需要找到来自一个源S的最短路径，通过N个边缘。图形可以有循环，边缘权重可以是负数，并且允许路径不止一次通过顶点或边缘。
是否有一个有效的算法对于这个问题？
我尝试了什么：
现在当我知道最终顶点作为约束时，我只能计算最短路径，但现在我希望我的约束在路径经过的边数上，而不是在最终顶点上。
In my economics research I am currently dealing with a specific shortest path problem:
Given a directed deterministic dynamic graph with weights on the edges, I need to find the shortest path from one source S, which goes through N edges. The graph can have cycles, the edge weights could be negative, and the path is allowed to go through a vertex or edge more than once.
Is there an efficient algorithm for this problem?
What I have tried:
For now I can only compute shortest path when I know the final vertex as a constraint, but now I want my constraint to be on the number of edges the paths go through and not on the final vertex.
推荐答案
这个问题是否有一个有效的算法？
Is there an efficient algorithm for this problem?
没有，更糟糕的是因为无限循环而无法解决。
None, even worse there can be no solution because of infinite looping.
图表可以有周期，边缘权重可以是负数，并允许路径多次通过顶点或边缘。
The graph can have cycles, the edge weights could be negative, and the path is allowed to go through a vertex or edge more than once.
这些标准的组合可能导致无限e循环。
如果你有一个负成本的循环，只需一个循环就可以无限地改善任何最佳路径。
负数成本阻止任何优化。
您必须重新考虑您的标准或提供详细信息。
The combination of those criteria can lead to infinite loops.
If you have a loop with negative cost, just 1 more loop will improve any best path infinitely.
Negatives costs prevent any optimization.
You have to rethink your criteria or give details.
这篇关于从一个来源经过N个边缘的最短路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
