我目前正在解决以下问题：给定一个有向图G = ( V , E )，我使用 Dijkstra 算法来找到每个节点v i ∈ V到 startnode v 0的最短距离d i。
现在我想找到节点 *v** ，其中所有节点最短距离 ∑<em>d i与该节点的总和最小化。
在下面的例子中，起始节点v 0是黄色的，显然距离为 0。给出了所有其他节点的最短距离。
在第一个图中（左下角的起始节点）所有最短距离的总和是
∑<em>d i = 1+2+2+2+3+3+3 = 16
在第二个图中（中间的起始节点）所有最短距离的总和是
∑<em>d i = 1+1+1+2+2+2+2 = 11
边权重是浮点数，在示例中，为了简单起见，它们被选为 1。
显然我可以尝试让每个节点都找到最小值，但这当然太慢了。我迫不及待地想听听你的想法！:-)
在社交网络的背景下，您所描述的中心性指标是由 Sadibussi 在 1966 年定义的（参见此处或此处的非官方链接。弗里曼在此处（第 225 页）也描述和推荐了作为分散性的衡量标准）。它有时被称为farness（见这里）。
广度优先搜索允许计算从图上每个顶点到其他顶点的最短路径的长度。在此处和此处查看已接受的答案。此处描述了计算所有对最短路径的其他方法。
编辑：
既然您注意到您对近似解决方案感兴趣，请查看 Baswana 和 Kavitha 的以下论文。表 1.1 总结了已知结果。迄今为止最好的近似解需要 O(n^(3/2)) 空间来进行 3 拉伸解（这意味着估计的距离将大于实际距离，但小于实际距离的 3 倍）。我想这对于大多数实际目的来说还不够好。没有已知的 APASP（All-Pairs Approximate Shortest Paths）算法具有伸展<3 且小于 O(n^2) 空间要求。
实际解决方案：