algorithm - 计算边缘连通性的有效算法？

Question

我想知道的是，是否有任何文献可供我阅读，用于确定给定图中所有边的边连通性的算法。

给定边的边连通性（正如我所理解的）是通过给定边的最短路径（差异节点之间）的数量。也就是说，如果我们要从每个节点到每个其他节点，我们将通过多少次给定的边。

任何帮助/资源将不胜感激

Answer 1

据我所知，这被称为边缘中介。这是一篇关于顶点介数的好算法的论文，它可以很容易地推广到边缘介数：

布兰德斯，乌尔里克 (2001)。“一种更快的中介中心性算法”（PDF）。数学社会学杂志 25: 163–177 http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf

Answer 2

使用 Dijkstra 算法找到最短路径。重复使用此算法来确定所有节点对的最短路径。现在您可以简单地总结每条路径中每条边的出现情况。