以圆为界的最短路径
Shortest Path Bounded By Circles
有 n 个半径为 r 的圆，第 i 个圆的原点位于 (x[i], y[i])。我想求出从第一个圆的原点到最后一个圆的原点的最短路径的距离，并且路径上的任意一点都在一个或多个圆的内部。
下面是位于(3, 3), (3, 7), (6, 7)三个圆圈的演示，蓝线是最短路径。
我试图找到每对圆的交点和 运行 最短路径算法，但这导致时间复杂度为 O(n^5)。我想知道是否存在更快 运行s 的更好算法。谢谢。
我找到了 O(n^3) 的解决方案。请注意，最佳路径由连接起点、终点或不位于另一个圆内的圆的交点（换句话说，图形的“外部交点”）的线段组成。候选点数为O(n).
然后对于每一对点，如果连接它们的直线上的每个点都在图中，则将这对点的距离标记为它们之间的直线距离。否则，将距离标记为无穷大。这需要 O(n^3) 因为有 O(n^2) 对点并且检查需要 O(n).
最后，运行任何从起始位置到结束位置的最短路径算法。 Floyd-Warshall 将是一个不错的选择，因为它的时间复杂度是 O(n^3) 并且给出了邻接矩阵。
有 n 个半径为 r 的圆，第 i 个圆的原点位于 (x[i], y[i])。我想求出从第一个圆的原点到最后一个圆的原点的最短路径的距离，并且路径上的任意一点都在一个或多个圆的内部。
下面是位于(3, 3), (3, 7), (6, 7)三个圆圈的演示，蓝线是最短路径。
我试图找到每对圆的交点和 运行 最短路径算法，但这导致时间复杂度为 O(n^5)。我想知道是否存在更快 运行s 的更好算法。谢谢。
我找到了 O(n^3) 的解决方案。请注意，最佳路径由连接起点、终点或不位于另一个圆内的圆的交点（换句话说，图形的“外部交点”）的线段组成。候选点数为O(n).
然后对于每一对点，如果连接它们的直线上的每个点都在图中，则将这对点的距离标记为它们之间的直线距离。否则，将距离标记为无穷大。这需要 O(n^3) 因为有 O(n^2) 对点并且检查需要 O(n).
最后，运行任何从起始位置到结束位置的最短路径算法。 Floyd-Warshall 将是一个不错的选择，因为它的时间复杂度是 O(n^3) 并且给出了邻接矩阵。