bha*_*mrc 6 algorithm graph-theory data-structures
在Graph中找到localbridge(k)的最佳算法是什么？度k的局部桥是边缘,其移除将其两个端点之间的最短距离扩大到至少k.
运行全最短路径成本算法，例如Floyd-Warshall 算法，但使用元组(d1,d2)表示距离，而不是典型的实数d：
d1是最短路径的长度d2是第二短路径的长度对 Floyd-Warshall 算法的修改应该很简单。
当您运行完所有最短路径成本算法后，边就是那些满足和之间的距离的localbridge(k)边。e = {u, v}(1,d2)uvd2 >= k