Thread: Quick Question - SPP, CPP, TSP

Hi,

I'm just having difficulities seeing the difference between the Shortest Path Problem, The Chinese Postman problem and the Travelling Sales man Problem.

I see they all wish to find the shortest path, and that the Chinese postman can use an egde more then once..but other then that I'm kind of confusd..

Thanks

Originally Posted by angels_symphony

Hi,

I'm just having difficulities seeing the difference between the Shortest Path Problem, The Chinese Postman problem and the Travelling Sales man Problem.

I see they all wish to find the shortest path, and that the Chinese postman can use an egde more then once..but other then that I'm kind of confusd..

Thanks

Shortest Path Problem: find the path between a given pair of vertices such
that the sum of the wights for this path is less than that for any other path
between the vertices.

Chinese Postman Problem: find the shortest closed path that visits all the
vertices.

Travelling Salesman Problem: find the shortest closed path that visits all the
vertices once only.

ZB