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 且小于您选择的特定值的范围。