我想知道如何为最短路径问题分配最大成本值。在我的问题中，节点与风险相关。因此，我希望最小化风险，但同时希望在找到解决方案时限制节点数量（例如，从节点A到节点B找到最小风险，同时确保解决方案不超过n个节点）。非常感谢。
3个回答
3
Dijkstra算法是最佳优先搜索，即我们应该确保到达最佳节点的距离永远不会变得更好。它适用于具有非负边缘的最小Dijkstra情况。在一般情况下，您可以使用Ford-Bellman。如果您想要使用不超过n个顶点，则可以建议您使用动态规划dp[vertex][used_vertex_count]，其复杂度为O（|V| * n）状态和内存以及O（|E| * n）时间。或者创建图的邻接矩阵，主对角线上为零，不存在边缘的地方为无穷大，并计算其n次幂。a_{ij}将是使用不超过n个顶点从i到j的最小路径。
- Artem Volkhin
0
我认为在这里使用一些涉及启发式的算法会更加适合，启发式是指每一步离目标有多“接近”的概念，以及哪个节点将使你更接近目标。如果没有这个，我认为我们需要在最坏情况下运行一个指数级算法（当只使用n个节点无法到达目标时）。在这种情况下，我们将查看所有使用n个节点的路径，然后才得出问题无法解决的结论。
使用非启发式算法的一个例子是：以常规方式运行Dijkstra算法，选择风险最小的节点。在此过程中，跟踪您访问的节点数量。如果节点数超过n，则放弃当前路线并回溯到先前的节点，并使用具有下一个最低风险的节点。自然地，您不能仅回溯到n的上一级，因为如果目标在下一级，则会被选中。因此，您要回溯到n-2级并继续进行。这也将是指数级的，因为没有真正的方法来确定不存在性而不检查所有路径。
也可能是我漏掉了什么。
- efficiencyIsBliss
-1
你想使用Prim算法，因为它可以在给定的图中找到所有最小生成树。然后，根据所需的约束条件轻松选择最小生成树。
- Micromega
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接