TSP Example

Q2.A salesman has to visit 5 cities the distance between the 5 cities are as follows:

                             To City
                          A         B         C         D           E

From City   A[infi         7            6          8            4
                   B 7         infi            8          5            6
                   C 6           8           infi         9            7
                   D 8           5            9        infi            8
                   E  4           6            7          8           infi]

If the sales man starts from city A and has to come back to his starting point which route should he select so that the total distance covered is minimum.

Soln:'

If we solve this problem, the final distance matrix will be.

           A             B               C              D           E
A      infi              3                0              4             0
B       3              infi                1              0             1
C       0               1                infi             2             0
D       4               0                  2            infi            3
E        0               1                  0             3           infi

The travel is given as A-->E-->B-->D-->C-->A

Distance=4+5+6+9+6
             =30 Km