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

Question

基本上，在权重为欧几里得距离的图中，是否真的需要像 Dijkstra 算法这样的算法，或者到达目的地的直接路径总是最短的吗？

我真的想问这个问题的一般性答案，但我认为对于下面给出的情况总是如此。

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

我几乎 100% 肯定如果边形成正多边形就是这种情况。

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

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

n = 5

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

n = 4

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

n = 3

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

Answer 1

这可能是一个反例：

n = 4

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

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

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

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

For positive weight directed graphs, in what case is the most direct path not the shortest?