Find Solution of Travelling salesman problem using diagonal completion method (MIN case)

Work\Job	A	B	C	D	E
A	x	2	5	7	1
B	6	x	3	8	2
C	8	7	x	4	7
D	12	4	6	x	5
E	1	3	2	8	x

Solution:
The number of rows = 5 and columns = 5

	`A`	`B`	`C`	`D`	`E`
`A`	M	2	5	7	1
`B`	6	M	3	8	2
`C`	8	7	M	4	7
`D`	12	4	6	M	5
`E`	1	3	2	8	M

Step-1: Find out the each row minimum element and subtract it from that row

	`1`	`2`	`3`	`4`	`5`
`1`	M	1	4	6	0	(-1)
`2`	4	M	1	6	0	(-2)
`3`	4	3	M	0	3	(-4)
`4`	8	0	2	M	1	(-4)
`5`	0	2	1	7	M	(-1)

Step-2: Find out the each column minimum element and subtract it from that column.

	`1`	`2`	`3`	`4`	`5`
`1`	M	1	3	6	0
`2`	4	M	0	6	0
`3`	4	3	M	0	3
`4`	8	0	1	M	1
`5`	0	2	0	7	M
	(-0)	(-0)	(-1)	(-0)	(-0)

Step-3: Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)

	`1`	`2`	`3`	`4`	`5`
`1`	`M`	`1`	`3`	`6`	`0^(color{red}{(1)})`
`2`	`4`	`M`	`0^(color{red}{(0)})`	`6`	`0^(color{red}{(0)})`
`3`	`4`	`3`	`M`	`0^(color{red}{(9)})`	`3`
`4`	`8`	`0^(color{red}{(2)})`	`1`	`M`	`1`
`5`	`0^(color{red}{(4)})`	`2`	`0^(color{red}{(0)})`	`7`	`M`

Step-4: List the penalties `P(i,j)` in descending order by value.

`P(3,4)=9`

`P(5,1)=4`

`P(4,2)=2`

`P(1,5)=1`

`P(2,3)=0`

`P(2,5)=0`

`P(5,3)=0`

Step-5: The links `(3,4),(5,1),(4,2),(2,3)` are selected for inclusion in the feasible partial tour.

Step-6: Feasible partial tour contains the following chains
`3->4->2,5->1`

`(2,3),(1,5)` can not be selected, because they are the closing links and create prohibited subtours.

Step-7: The new submatrix is :

	`3`	`5`
`2`	M	2
`1`	5	M

---

Repeat from step-1 to step-7
Step-1: Find out the each row minimum element and subtract it from that row

	`3`	`5`
`2`	M	0	(-2)
`1`	0	M	(-5)

Step-3: Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)

	`3`	`5`
`2`	`M`	`0^(color{red}{(0)})`
`1`	`0^(color{red}{(0)})`	`M`

Step-4: List the penalties `P(i,j)` in descending order by value.

`P(2,5)=0`

`P(1,3)=0`

Step-5: The links `(2,5),(1,3)` are selected for inclusion in the feasible partial tour.

Step-6: Feasible partial tour contains the following chains
`3->4->2->5->1->3`

So our final path is `C->D->B->E->A->C`

and total distance is `4+4+2+1+5=16`

---

---