1

假设给定一个加权有向图G = ( V , E )，其中有n 个节点，其中p是中心节点。让C , | C | = p 是中心节点的集合，N = V \ C是非中心节点的集合。边e ij的值是有限非负实数，如果：

  1. i来自集合N，而j来自集合P，或
  2. i来自集合P，而j来自集合P，或者
  3. i来自集合P，而j来自集合N。

否则，如果i来自集合N并且j来自集合N，则e ij的值等于正无穷大。

我们有兴趣在图G中找到所有最短距离的最大值。我发现解决这个问题的最快算法是使用对 Floyd-Warshall 算法的简单修改，该算法在O ( n 2 p ) 中运行。这是简单的伪代码：

FOR ALL k FROM the set C DO
  FOR ALL i FROM the set V DO
    FOR ALL j FROM the set V DO 
      e[i, j] = MIN(e[i, j], e[i, k] + e[k, j])
-----------------------------------------------
result = 0
FOR ALL i FROM the set V DO
  FOR ALL j FROM the set V DO
    result = MAX(result, e[i, j])
-----------------------------------------------
RETURN result

可能没有比这更快的算法了。（或者，我错了吗？:)）

但是，我对以下内容更感兴趣，我认为这里有更快的东西。假设我们只是从集合C和N中交换两个节点，即。对于来自C的一些v c和来自N的一些v n，集合C变为C + v n - v c并且集合N变为N + v c - v n。现在，我们感兴趣的是在G中的所有最短距离上找到新的最大距离。

我知道的更快的算法是简单地使用描述的 Floyd-Warshall 方法从一开始计算新的最大距离，该方法在O ( n 2 p ) 中再次运行。有没有更快的计算方法，可能在交换节点之前使用最短距离的旧计算值？

4

0 回答 0