algorithm - 寻找 Dijkstra 算法的起始顶点？

Question

想象一下，我正在公园里实现 Dijkstra 算法。这些点之间有点和联系；这些指定了用户可以行走的有效路径(例如人行道)。

现在假设用户在草地上(即不在路径上)并且想要导航到另一个位置。问题不在于 Dijkstra 算法(它工作正常)，问题在于确定从哪个顶点开始。

这是问题的图片:(暂时忽略虚线)

黑线 显示 Dijkstra 算法中的边缘；同样，紫色圆圈 显示顶点。人行道为灰色。您猜对了，草是绿色。用户位于红星，想要到达橙色X。

如果我天真地寻找最近的顶点并将其用作我的起点，用户通常会被引导到次优路径，这涉及在开始时远离他们的目的地(即红色实心路径).

蓝色实线路径是我的算法理想中得出的最佳路径。

注意事项:

• 假设没有路径与其他路径交叉。
• 当导航到起点时，用户不应越过路径(例如人行道)。
• 在上图中，从星形出来的第一条线段是动态创建的，只是为了帮助用户。星号不是图中的顶点(因为用户可以位于草地区域内的任何位置)。仅显示从星形到顶点的线段，以便用户知道如何到达图中的第一个有效顶点。

我怎样才能有效、正确地实现它？

---

想法 #1:找到封闭的多边形

如果找到围绕我的起点的最小多边形，我现在可以为 Dijkstra 算法创建从起点(将临时添加为新顶点)到构成多边形的每个顶点的新路径。在上面的示例中，多边形有 6 条边，因此这意味着要为它的每个顶点创建 6 条新路径(即蓝色虚线)。然后我将能够运行 Dijkstra 算法，它会很容易地确定蓝色实线是最佳路径。

此方法的问题在于确定哪些顶点构成了围绕我的点的最小多边形。我不能为图中的每个顶点创建新路径，否则我最终也会得到红色虚线，这完全违背了使用 Dijkstra 算法的目的(我不应该被允许交叉人行道)。因此，我必须注意只创建到封闭多边形顶点的路径。有这方面的算法吗？

此解决方案还有另一个复杂之处:假设用户现在从紫色闪电开始。它没有封闭的多边形，但通过将它连接到右上角的 3 个点，该算法应该仍然有效。同样，一旦连接到这些，运行 Dijkstra 就很容易了。
更新:我们想要连接到这 3 个点之一而不是绕过所有地方直接到达橙色 X 的原因是因为我们想尽量减少在未铺砌的路径上进行的步行。 (注意:如果您从多边形外开始，这只是一个限制条件。如果它在多边形内，我们不关心您在草地上走了多长时间)。

如果这是正确的解决方案，请发布其算法作为答案。

否则，请发布更好的解决方案。

Answer 1

您可以从目标开始运行 Dijkstra 以找到它到所有顶点的距离。

现在让我们考虑一下您从草地上的图形“内部”开始的情况。我们想找到所有可以通过直线到达而不穿过任何边的顶点。为此，我们可以将所有表示边的线段和将起点连接到每个顶点的线段放在一起，并使用 sweep-line algorithm。查找起始顶点线是否与任何边相交。

或者，您可以对 planar point location 使用任何离线算法，那些也适用于扫描线。我相信这符合问题中提出的更抽象算法的精神，因为它报告了围绕该点的多边形。

然后我们只需要找到与起点的连线不与任何边相交且d(vertex, target) + d(vertex, start)之和最小的顶点。

当顶点在图外时的过程有点不明确，但我想完全相同的想法会起作用。请记住，如果目标位于边界上，则有可能绕过图形到达目标，就像在您的示例中一样。

这可能可以在每个查询的 O((n+m) log m) 中实现。如果你运行 all-pairs shortest path algorithm作为预处理步骤并使用在线点定位算法，您可以以存储信息所需的空间为代价获得对数查询时间，以加速最短路径查询(如果您只存储所有距离对，则为二次)。

我相信简单的平面点定位就像扫描线方法一样工作，仅适用于 persistent用于存储所有扫掠线状态的 BST。