在图中找到最近的标记节点

Question

在一个包含多个普通节点和几个特殊标记节点的图中，是否有通用算法可以找到距离给定起始位置最近的标记节点？

或者最好的方法是使用广度优先搜索查找标记节点，然后对每个发现的标记节点执行Dijkstra算法，以确定哪个是最近的节点？

- John Slaine

---

请问您能否在问题中添加更多细节？这个图是有向的吗？也许您有一个常量（或很少变化）的图和许多查询？还是每次都有一个新的问题实例？您对标记顶点的数量有任何限制吗？ - DAle

请问您能否定义“closest”一词。是指空间上最近的、网络跳数最少的、最短的网络距离还是其他什么？ - SaiBot

@SaiBot 我所说的“更接近”是指从起始节点开始，需要跨越的边最少的节点。 - John Slaine

Answer 1

这取决于图形和你对“最接近”的定义。如果忽略边权重或者你的图没有边权重，那么简单的广度优先搜索（BFS）就足够了。通过 BFS 达到的第一个节点是最接近的（或者，如果有几个最接近的节点，则距离相等）。如果你跟踪扩展的 BFS 级别数量，可以到达级别末尾来定位所有最接近的节点，而不是在找到第一个标记节点后停止。

如果你有边权重，并需要在计算中使用它们，请改用 Dijkstra。如果边可以具有负权重，并且存在任何负循环，则需要改用 Bellman-Ford。

如SaiBot所述，如果起始节点始终相同，并且您将执行多个查询以更改“标记”节点，则有更快的方法来完成任务。特别地，您可以在每个节点中存储在第一次完整遍历中找到的“父”和节点到起始节点的距离。当添加新批次的k个标记节点时，您可以通过查看每个标记节点的此距离立即知道最靠近起点的节点。

- tucuxi

---

如果你增加一个常数，Dijkstra 算法就不能处理带有负权边的图。 - DPDP

@tucuxi 是的，这个图是无权图。在这种情况下，BFS 怎么使用呢？它会在找到一个标记节点后停止，因为那将是最近的节点，对吧？ - John Slaine

如果您有一个启发式算法，您也可以通过将启发式算法设置为所有终点节点的最小值来使用A*算法。 - BlueRaja - Danny Pflughoeft

@noJS 谢谢，自从我读理论以来已经很长时间了，现在我正在纠正我的答案。Bellman-Ford算法就是它！ - tucuxi

@JohnSlaine澄清了BFS答案。是的，找到的第一个最接近（或相等）。如果您跟踪级别（=从开始跳转）并完成级别，则可以找到所有最接近的标记节点。 - tucuxi

Answer 2

最快的方法是从起始位置（起始节点）直接执行Dijkstra算法。当“接近程度”被定义为必须遍历的边数时，您可以将每条边的权重赋值为1。如果允许预计算，则有更快的方法来完成它。

- SaiBot