如何限制最短路径 - dijkstra算法的最大代价？

Question

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

Answer 1

Dijkstra算法最好先搜索，即我们应该肯定的是，以最好的节点的距离永远不会变得更好。它适用于具有非负边的最小Dijkstra。在一般情况下，您可以使用Ford-Bellman。如果你想使用不超过n个顶点，我可以建议你采用动态规划DP [顶] [used_vertex_count]与复杂度为O（| V | * n）的状态和内存和O（| E | * n）的时间。或者创建图形的邻接矩阵，其中主对角线上的零点和缺少边缘的无穷远点并计算它的n指数。 a_ {ij}将使用不超过n个顶点从i到j的最小路径。

Answer 2

我认为一些算法，包括启发式会得到更好的适合这里，启发式是如何“接近”你是在每一步的目标的一个概念，哪个节点将带你更接近球门。如果没有这些，我认为我们需要在最坏的情况下运行一个指数算法（当只使用n节点无法达到目标时，我们会在所有使用n节点的路径之前得出结论该问题无法解决）。

使用非启发式算法的一个例子是：以常规方式运行Dijkstra's，选择最小风险的节点。一路上，跟踪您访问过的节点数量。如果节点数超过n，则放弃当前路由并回溯到前一个节点，并使用具有次低风险的节点。当然，你不能仅仅回溯到n以上的一个等级，因为如果目标是在下一个等级中的话，它就会被挑选出来。因此，你回到n-2水平并继续。这也将是指数性的，因为没有检查所有路径来确定不存在的真实方式。

这也可能是我想的东西。

Answer 3

你想用Prim算法，因为它发现在给定的图全部最小生成树。然后很容易选择具有所需约束的mst。