algorithm - 最短路径算法 : multiple source, 最近的目的地

Question

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

我想扩展它以找到图形上源的“重心”，即“最接近”一组源的顶点，找到“公平”路径到一个“双方同意”的顶点。

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

Answer 1

Floyd–Warshall algorithm

我认为您想计算源(S1、S2、...Sn-1、Sn)的“图形偏心率”。

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

更多信息:

Graph Eccentricity

更新

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