# Quick Question - SPP, CPP, TSP

• Dec 16th 2007, 11:07 PM
angels_symphony
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
• Dec 17th 2007, 08:49 PM
Constatine11
Quote:

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