最短路径算法：多源，最近的目的地

Question

存在 Bellman-Ford 算法和 Dijkstra 算法等算法，用于查找从图上的单个起始顶点到所有其他顶点的最短路径。它们的多源版本可以通过反转所有边并将目标视为起始节点来实现。

我想扩展它以找到图上源的"barycentre"，即 "closest" 到集合的顶点源，找到 "fair" 到 "consensual" 顶点的路径。

是否已有算法提供此功能？它们是什么？

Answer 1

Floyd–Warshall algorithm

我想你想计算 来源 (S1,S2,...Sn-1,Sn) 的 "Graph Eccentricity"。

1. 使用Floyd-Warshall算法计算图中所有对的最短路径。
2. 求图中结果节点V，即(d[v,S1]+d[v,S2]+d[v,S3]....d[v,Sn- 1]+d[v,Sn])

更多信息：

Graph Eccentricity

更新

也许在Graph G(V,E)中找到一个到S的距离都相等的节点v是不现实的。您可以计算 (d[v,S1],d[v,S2],d[v,S3]...d[v,Sn-1],d[v,Sn])大于或等于 0 且小于您选择的某个值的范围。