所以我有一个近似表面的三角形网格。
它就像一个具有以下属性的图表：
- 图边界上的顶点很容易识别。（相邻顶点数 > 包含三角形数）
- 您可以轻松计算任意两个顶点之间的距离。（欧几里得距离）
- 对于任何顶点v，任何不是 v 邻居的顶点到v的距离必须大于v的至少一个邻居的距离。换句话说，在v的邻域环内不能出现非邻域顶点。
对于每个顶点v，我想计算从 v 到任何边界顶点的最小距离。
我可以通过蛮力做到这一点，建立所有边界顶点的列表，比较v与每个顶点的距离，并保持最小值。但这是低效的。
我相信对于每个单个顶点v最有效的方法是有一个优先级队列，其中顶部元素最接近v。队列用v的邻居初始化。当队列的顶部不是边界顶点时，弹出顶部并推送弹出顶点的所有邻居。
假设顶点v有 6 个邻居，我计算这 6 个邻居中的每一个的最小边界距离，并记录为 6 个邻居提供最小值的确切边界顶点。我知道其中之一还必须给出v的最小边界值。我无法真正证明这一点，但我认为这是直观的。如果v被它的邻居包围，那么离v最近的边界顶点也必须是离它的一个邻居最近的边界顶点。
我想知道是否有办法使用这些知识来有效地计算图中每个点的最小值。比从每个顶点进行广度优先搜索更有效。