CODEWITHSUNDEEP
algorithmpath-findingdirected-graph
KthProg
KthProg

Reputation: 2117

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

Basically, in a graph where the weights are the Euclidean distance, is something like Dijkstra's algorithm really necessary or is a direct path to your destination always the shortest?

I'm really asking for a general answer to this question, however I think this is always true for the case given below.

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

I'm almost 100% sure that this is the case if the edges form regular polygons.

These paths have no dead ends, i.e., there exists some path from any vertex v1 to any other vertex v2.

By regular polygon I mean the graph is formed by edge connection of regular polygons of n vertices, without ever forming other polygons in the process.

n = 5

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

n = 4

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

n = 3

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

Upvotes: 1

Views: 149

Answers (1)

KthProg
KthProg

Reputation: 2117

This may be a counterexample:

n = 4

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

Basically, if there is any non-symmetrical gap in the graph, then the greedy algorithm, which always selects the nearest vertex to the end vertex, may select a vertex which forces it to take a longer path.

However, the greedy algorithm will always work for paths with no obstacles, or paths with symmetrical obstacles if the starting point halves the obstacle. In fact, an algorithm which could simply find the shortest path around each individual obstacle would provide solutions nearly as good as Dijkstra's without as much overhead, as long as there are no dead ends.

But implementing such an algorithm is the same as implementing Dijkstra's on sub-paths of the total path, and is therefore pretty pointless, unless you really need to reduce the computational resources required.

Upvotes: 1

Related Questions