algorithm - 与其他 n 个顶点距离最小的顶点

给定一个有向加权循环图和由 m(x,y) 给出的顶点之间的最小路径距离，找到最小化 m(a,v) + m(b,v) + m(c,v) 的顶点 v + ... 对于 n 个顶点 a, b, c...

例如，如果图是无向的，并且我们希望顶点 v 具有到顶点 a 和 b 的最小路径，则 v 将只是从 a 到 b 的最小路径中心的顶点。

我可以想象一种涉及深度遍历等的方法，但想问一下 SO 会建议什么 - 谢谢希望这很清楚。

标签： algorithmgraph

现在我正在考虑更多关于它的内容，您可能应该看看Bidirectional Search。

基本思想是同时从每个查询节点（a、b、c、...）启动 Dijkstra。他们所有人找到的第一个顶点是您的结果顶点。

您可以通过将遇到的所有（未访问的顶点、距离、查询顶点）三元组放入一个优先级队列（按距离排序）并与 Dijkstra 类似的处理来实现这一点。您将需要使用您到达它们的查询节点来标记您看到的顶点。当一个顶点被所有查询顶点标记时，这就是你的结果（我们称之为中间顶点）。