CODEWITHSUNDEEP
pythonalgorithm
Wizard
Wizard

Reputation: 22113

`the shortest path that connects several points` NP-complete algorithms

I am reading `Grokking algorithms" and understand Dijkstran and greedy algorithms,
but, when the author compare them with NP-complete problem

But it’s hard to tell if a problem you’re working on is NP-complete. Usually there’s a very small difference between a problem that’s easy to solve and an NP-complete problem. For example, in the previous chapters, I talked a lot about shortest paths. You know how to calculate the shortest way to get from point A to point B.
enter image description here But if you want to find the shortest path that connects several points, that’s the traveling-salesperson problem, which is NP-complete. The short answer: there’s no easy way to tell if the problem you’re working on is NP-complete. Here are some giveaways:

The sentence:
But if you want to find the shortest path that connects several points,

What are "the several points"?
I cannot figure out any difference with a basic Dijkstan's algorithms problem.

Upvotes: 0

Views: 170

Answers (1)

Serge
Serge

Reputation: 3765

He means a path through a subset of all the nodes of a graph, I think. (Think the worst case of 'several points')

Note, that for any fixed number of points, say k = 3 or k = 3000 on a graph of n nodes, the problem would be of the same complexity as for two points. While some people may think that several is never greater than seven, or may be seven dozens or seven billion, it is neither a matter of fact nor an exact science.

Less likely he meant the usual formulation of the Traveling salesman problem (all the nodes/points on a connected graph), though a possibility. NP complete any way.

Upvotes: 1

Related Questions