algorithm - 对于正权有向图，什么情况下最直接的路径不是最短的？

Question

基本上，在权重为欧几里得距离的图中，Dijkstra 算法之类的东西是否真的有必要，或者到达目的地的直接路径总是最短的？

我真的要求对这个问题有一个笼统的回答，但我认为对于下面给出的案例来说，这总是正确的。

==================================

如果边形成正多边形，我几乎 100% 肯定会出现这种情况。

这些路径没有死角，即存在从任何顶点 v1 到任何其他顶点 v2 的路径。

我所说的正多边形是指图形是由 n 个顶点的正多边形的边连接形成的，在此过程中从未形成其他多边形。

n = 5

 . .
.   .
  .   .
   . .
  .   .
    .   .
     . .

n = 4

    . . . .
  . . . . .
  . . .
    . .

n = 3

  .     . .
 . . . . . .
. . . .   . .

Answer 1

这可能是一个反例:

n = 4

. . . . . . . .
. . . . .   . .
. . . . .   . .
. . .       . .
. . . . .   . .
. . . . .   . .
. . . . .   . . 
. . . . . . . .
. . . . . . . . 

基本上，如果图中存在任何非对称间隙，那么总是选择离结束顶点最近的顶点的贪心算法可能会选择一个顶点，迫使它采取一个更长的路径。

然而，贪心算法将始终适用于没有障碍物的路径，或者如果起点将障碍物减半则具有对称障碍物的路径。事实上，只要没有死胡同，只需找到绕过每个障碍物的最短路径的算法就可以提供与 Dijkstra 算法几乎一样好的解决方案，而不会产生太多开销。

但实现这样的算法与在总路径的子路径上实现 Dijkstra 算法相同，因此毫无意义，除非您确实需要减少所需的计算资源。