有向加权边图及其权值算法

Question

我有一个有向图，边上有非负权重。

我的算法应该执行以下操作：

• 获取从顶点u到顶点v的所有路径。
• 计算从u到v的每条路径上的最小加权边。
• 计算上面计算的最小加权边的最大值。

什么算法对此有好处？我之所以这样问，是因为我可以天真地执行上面的步骤，就像我已经说过的(蛮力)。

我觉得这是对Dijkstra算法的轻微修改，但我不确定。而且，时间的复杂性是什么？

Answer 1

我想我们不需要dijkstra了。假设我们选择了具有所需的最小最大边缘的路径。它显然不包括重量较小的边。所以算法是

• 选择K最重的边缘
• 使用dfs/bfs检查v是否可从u通过此边缘到达(f(K) is true)
• 如果K1>K2和f(K2) is true，那么显然是f(K1) is true
• 所以我们可以在K上运行二进制搜索

时间复杂度为O((N+M) log M)，其中N -顶点数和M -边数。

Answer 2

任何实际考虑从u到v的所有路径的算法都需要指数时间，因为这样的路径有一个指数型数--考虑一个阶梯，或者一个由2xN节点组成的网格--在你至少有N个独立选择的长维中从一端到另一端，所以至少有2^N个可能的路径。

我认为你可以修改Dijkstra的算法来做到这一点。algorithm#Pseudocode有psuedocode。作为第一次修改，将第6行更改为将所有初始距离设置为零。我们需要考虑不变量，我们的第一个不变量可以是，对于到目前为止所看到的所有路径，distv是路径中最小边的最大值。和以前一样，我们将prevv设置为undefined，并将v添加到Q，这是当前正在考虑的所有节点的队列。作为初始化的最后一部分，我们设置了distsource =无穷大-而不是0。您可以认为这是一种黑客，或者是一种在长度从v到v的路径中定义没有任何边的最小边长度的方法。

现在我们有了q包含所有节点，其中最小边的最大值仍在考虑中，并且所有这些节点的这个值都只会增加。现在，我们从q中移除具有distu最大值的节点u，这是修改步骤13，将min更改为最大值。对于u的每个邻域v，我们计算min(distv，长度(u，v))。这是一个新的候选的最大可能的最小边缘长度沿任何路径从源到u，因此，如果这是大于distu，我们将distu设置为这个值。请注意，这意味着q的任何元素u都不会被设置为比我们刚刚删除的q的元素v的distv值更大的值，这是队列中的最大值。这意味着，一旦我们从队列中删除了一个元素v，它的值be就被计算得很好，并且不能通过任何后续的计算来增加。注意，我们刚刚为队列中的一个节点更改了distu。如果Q是用诸如优先级队列之类的数据结构实现的，这可能意味着实现必须从旧的distu值下的优先级队列中移除u，然后在distu的新值下重新插入它。

正确性来自不变量--每次我们在考虑的每条路径上都有最小边的最大值，当我们从队列中删除v时--因为它对队列中的所有东西都有最大值--我们可以考虑的其他路径都不可能改变这个值。

做这件事所花的时间和Dijkstra一样，也是出于同样的原因。在开始时，我们将每个元素输入队列一次，然后从队列中删除每个元素一次。这将告诉我们在第14行中执行remove操作的次数。

(最小加权边的最大值似乎是一件很奇怪的事情--这里有一个有趣的应用程序吗，或者这是一种人工练习，可以让您思考Dijkstra的算法？)