Для положительных весовых графов, в каком случае самый прямой путь не самый короткий?

Question

В принципе, в графе, где веса являются евклидовым расстоянием, что-то вроде алгоритма Дейкстры действительно необходимо или является прямым путем к вашему месту назначения, всегда кратчайшему?

Я действительно прошу дать общий ответ на этот вопрос, однако я думаю, что это всегда верно для случая, приведенного ниже.

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

Я почти на 100% уверен, что это так, если ребра образуют правильные многоугольники.

Эти пути не имеют мертвых концов, т. Е. Существует какой-либо путь от любой вершины v1 к любой другой вершине v2.

Правильный многоугольник Я имею в виду, что граф образован граничным соединением правильных многоугольников n вершин, не создавая при этом других полигонов.

n = 5

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

n = 4

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

n = 3

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

Answer 1

Это может быть противоречащий:

n = 4

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

В принципе, если есть какой-либо несимметричный разрыв в графике, то жадный алгоритм, который всегда выбирает ближайшую вершину до конечной вершины, может выбрать вершину, которая заставляет его взять более длинный путь.

Однако жадный алгоритм всегда будет работать на пути без препятствий или пути с симметричными препятствиями, если начальная точка уменьшит препятствие. Фактически, алгоритм, который мог бы просто найти кратчайший путь вокруг каждого отдельного препятствия, обеспечил бы решения, почти такие же хорошие, как у Дейкстры, без стольких накладных расходов, если нет мертвых концов.

Но реализация такого алгоритма такая же, как реализация Dijkstra на подпутьх полного пути и, следовательно, довольно бессмысленна, если вам действительно не нужно уменьшать требуемые вычислительные ресурсы.