algorithm - 如何以最大成本限制最短路径 - dijkstra 算法？

Question

我想知道如何为最短路径问题分配最大成本值。在我的问题中，我有与节点相关的风险。所以我想将风险降到最低，但同时我希望它找到一个节点数量有限的解决方案。（例如，找到从节点 A 到节点 B 的最小风险，同时确保解决方案不超过 n 个节点）谢谢很多。

Answer 1

Dijkstra 是最佳优先搜索，即我们应该确定，到最佳节点的距离永远不会变得更好。它适用于具有非负边缘的最小 Dijkstra。在一般情况下，您可以使用Ford-Bellman。如果您想使用不超过 n 个顶点，我可以建议您动态编程 dp[vertex][used_vertex_count] 复杂度为 O(|V| * n) 状态和内存以及 O(|E| * n) 时间。或者创建图的邻接矩阵，在主对角线上为零，并且无穷大插入不存在的边并计算它的 n 指数。a_{ij} 将是从 i 到 j 的最小路径，使用不超过 n 个顶点。

Answer 2

我认为一些涉及启发式的算法最适合这里，启发式是关于你在每一步中离目标有多“接近”的概念，以及哪个节点会让你更接近目标。没有它，我认为我们需要在最坏的情况下运行指数算法（即仅使用节点无法达到目标时n。在这种情况下，我们将查看所有使用n节点的路径，然后才能得出问题的结论无法解决）。

使用非启发式算法的一个示例是：以常规方式运行 Dijkstra，选择风险最小的节点。在此过程中，跟踪您访问过的节点数量。如果节点的数量超过了，n那么放弃您当前的路线并回溯到前一个节点并使用具有下一个最低风险的节点。当然，你不能只回溯上一层n，因为如果目标在下一层，它就会被选中。因此，您回溯到水平n-2并继续。这也将是指数级的，因为没有一种真正的方法可以在不检查所有路径的情况下确定不存在。

也可能是我错过了一些东西。

Answer 3

您想使用 Prim 算法，因为它会在给定图中找到所有最小生成树。然后很容易选择具有所需约束的 mst。