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

Work\Job	1	2	3	4
1	x	4	9	5
2	6	x	4	8
3	9	4	x	9
4	5	8	9	x

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

	`1`	`2`	`3`	`4`
`1`	M	4	9	5
`2`	6	M	4	8
`3`	9	4	M	9
`4`	5	8	9	M

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

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

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

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

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

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

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

`P(2,3)=6`

`P(4,1)=5`

`P(3,2)=4`

`P(1,4)=3`

`P(1,2)=0`

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

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

So our final path is `4->1->2->3->4`

and total distance is `5+4+4+9=22`

---

---