CODEWITHSUNDEEP
shortest-path
User123456789
User123456789

Reputation: 149

Elementary shortest path problem vs. shortest path problem

What is the difference between an elementary shortest path problem and shortest path problem?

A shortest path problem, is solved by finding the shortest path from a source node s to a target node t in a graph.

A simple shortest path problem, is solved by finding the shortest path from a source node s to a target node t in a graph, such that each arc in the shortest path is used at most 1 time.

What is an elementary shortest path?

Upvotes: 1

Views: 963

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

The term "elementary shortest path" means "a shortest path that doesn't repeat any nodes or edges." If you're looking to compute the shortest path from one node to another in a graph with no negative cycles, then there's no difference between "shortest path" and "elementary shortest path," since they mean the same thing. However, "shortest path" in other contexts might not be the same as "elementary shortest path." For example:

  • If your goal is to find a path that starts at some node s, ends at some node t, and visits all the nodes in some set X along the way, the shortest path that does so may not be the same as the elementary shortest path. There may not even be an elementary shortest path that accomplishes this goal, depending on the shape of the graph.
  • If the graph has negative cycles, then the notion of "the shortest path from s to t" might not be mathematically well-defined, because following a negative cycle over and over and over will keep dropping the cost. However, the "elementary shortest path" may is defined provided there's a path from s to t, since you can't follow negative cycles.

Hope this helps!

Upvotes: 2

Related Questions