6

在 Graph 中找到 localbridge(k) 的最佳算法是什么？度数为 k 的局部桥是一条边，其移除会将其两个端点之间的最短距离扩大到至少 k。

维基百科：http ://en.wikipedia.org/wiki/Bridge_(interpersonal)#Local_bridge

4

1 回答 1

2

运行全最短路径成本算法，例如Floyd-Warshall 算法，但在距离使用元组(d1,d2)而不是典型实数的地方d：

  • d1是最短路径的长度
  • d2是第二最短路径的长度

对 Floyd-Warshall 算法的这种修改应该很简单。

当您完成运行所有最短路径成本算法时，localbridge(k)边是那些边e = {u, v}，使得和(1,d2)之间的距离满足。uvd2 >= k

于 2013-06-21T16:01:48.193 回答