像Bellman-Ford算法和Dijkstra算法这样的算法用于找到从图上的单个起始顶点到每个其他顶点的最短路径 . 它们的多源版本可以通过反转所有边缘并将目标作为起始节点来实现 .
我想扩展它以找到图上的源的"barycentre"，即到一组源的"closest"的顶点，找到"fair"到"consensual"顶点的路径 .
是否有算法提供此功能？这些是什么？
Floyd–Warshall algorithm
我想你要计算 the sources 的"Graph Eccentricity"（S1，S2，...... Sn-1，Sn） .
使用Floyd-Warshall算法计算图中的所有最短路径对 .
在图中找到结果节点V，它是（d [v，S1] d [v，S2] d [v，S3] ...... d [v，Sn-1] d [v的最小和 . SN]）
更多信息：
Graph Eccentricity
UPDATE
也许找到一个已存在的节点v在图G（V，E）中，到 S 的距离都相等是不现实的 . 您可以计算a之间（d [v，S1]，d [v，S2]，d [v，S3] ...... d [v，Sn-1]，d [v，Sn]）的Stand Standiation范围大于或等于0且小于您选择的某个值 .
1 回答
Floyd–Warshall algorithm
我想你要计算 the sources 的"Graph Eccentricity"（S1，S2，...... Sn-1，Sn） .
使用Floyd-Warshall算法计算图中的所有最短路径对 .
在图中找到结果节点V，它是（d [v，S1] d [v，S2] d [v，S3] ...... d [v，Sn-1] d [v的最小和 . SN]）
更多信息：
Graph Eccentricity
UPDATE
也许找到一个已存在的节点v在图G（V，E）中，到 S 的距离都相等是不现实的 . 您可以计算a之间（d [v，S1]，d [v，S2]，d [v，S3] ...... d [v，Sn-1]，d [v，Sn]）的Stand Standiation范围大于或等于0且小于您选择的某个值 .