如何限制最短路径 - dijkstra算法以最大成本？
我想知道如何为最短路径问题分配最大成本值。在我的问题中，我存在与节点相关的风险。所以我想最小化风险，但同时我希望它找到一个节点数量有限的解决方案。（例如，找到从节点 A 到节点 B 的最小风险，同时确保解决方案不超过 n 个节点）谢谢很多。
I am wondering how I can assign a maximum cost value for the shortest path problem. In my problem, I have risks associated with nodes. So I would like to minimize risk, but while doind that I want it to find a solution with limited number of nodes.(eg. find minimum risk from node A to node B, while ensuring solution does not exceed n number of nodes) Thanks a lot.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Dijkstra 是最佳优先搜索，即我们应该确定，到最佳节点的距离永远不会变得更好。它适用于具有非负边的最小 Dijkstra。一般情况下，您可以使用 Ford-Bellman。如果您想使用不超过 n 个顶点，我可以建议您使用复杂度为 O(|V| * n) 状态和内存以及 O(|E| * n) 时间的动态编程 dp[vertex][used_vertex_count] 。或者创建图的邻接矩阵，主对角线上为零，无穷大插入缺失的边，并计算它的 n 指数。 a_{ij} 将是从 i 到 j 的最小路径，使用不超过 n 个顶点。
Dijkstra is Best First Search, i.e. we should be sure, that distance to the best node never will become better. It works for minimum-Dijkstra with non-negative edges. In general case you can use Ford-Bellman. In case you want to use not more than n vertexes, i can suggest you Dynamic programming dp[vertex][used_vertex_count] with complexity O(|V| * n) states and memory and O(|E| * n) time. Or create adjacency matrix of the graph with zeros on main diagonal and infinity insted of absent edge and calc it's n exponent. a_{ij} will be min path from i to j using no more than n vertexes.
我认为一些涉及启发式的算法最适合这里，启发式是你在每一步中距离目标有多“接近”的概念，以及哪个节点会让你更接近目标。如果没有这个，我认为我们需要在最坏的情况下运行指数算法（即仅使用 n 个节点无法达到目标时）。在这种情况下，我们将查看所有路径在我们得出问题无法解决之前使用
n个节点）。使用非启发式算法的一个示例是：以常规方式运行 Dijkstra，选择风险最小的节点。一路上，跟踪您访问过的节点数量。如果节点数量超过
n，则放弃当前路线并回溯到前一个节点，并使用风险次低的节点。当然，您不能仅回溯到n以上一个级别，因为如果目标位于下一个级别，那么它就会被选中。因此，您回溯到n-2级别并继续。这也将是指数级的，因为没有一种真正的方法可以在不检查所有路径的情况下确定不存在。也可能是我遗漏了一些东西。
I think that some algorithm that involves heuristics would be best suited here, the heuristic being a notion of how "close" to the goal you are at each step, and which node will take you closer to the goal. Without that, I think we would need to run an exponential algorithm in the worst case (which would be when the goal cannot be reached using just
nnodes. In this case, we will look at all paths that usennodes before we conclude that the problem cannot be solved).One example of using a non-heuristic algorithm is this: Run Dijkstra's in a regular fashion selecting the node with min risk. Along the way, keep track of the number of nodes you have visited. If the number of nodes goes beyond
nthen abandon your current route and backtrack to a previous node and use the node with the next lowest risk. Naturally, you can't backtrack just one level aboven, since if the goal were in the next level, it would have been picked. Therefore, you backtrack to leveln-2and carry on. This too will be exponential as there isn't a real way to determine non-existence without checking all paths.It could also be that I'm missing something.
您想要使用 Prim 算法，因为它会找到给定图中的所有最小生成树。然后很容易选择具有所需约束的 mst。
You want to use Prim's algorithm because it finds all minimal spanning tree in the given graph. Then it is easy to select the mst with the desired constraint.