Algorytm Craft

Macierz przepływów

	1	2	3	4	5
1	X	650	200	0	0
2	650	X	450	400	0
3	200	450	X	350	300
4	0	400	350	x	150
5	0	0	300	150	x

Macierz odległości

	1	2	3	4	5
1	X	4	2,5	1,5	3,5
2	4	X	1,5	2,5	3,5
3	2,5	1,5	X	3	5
4	1,5	2,5	3	x	2
5	3,5	3,5	5	2	x

Q= (S1,2*L1,2)+Q1,3+Q1,4+ Q1,5+Q2,3+Q2,4+Q2,5+Q3,4+Q3,5+Q4,5=
∆Q1,2=(S1,3-S2,3)*(L1,3-L2,3) //co by było gdybyśmy zamienili jedynkę z dwójką w relacjach z trójką

∆Q1,2=(S1,3-S2,3)*(L1,3-L2,3)+(S1,4-S2,4)(L1,4-L2,4)+(S1,5-S2,5)(L1,5-L2,5)= (-2 50*1)+(-400)*(-1)+0*0= -250+400=150 //zmniejszamy pracę o 150

∆Q3,4=(S3,1-S4,1)*(L3,1-L4,1)+(S3,2-S4,2)(L3,2-L4,2)…= 600

∆Q3,5=-950 //Zwiększamy pracę o 950

∆Q4,5=-500
Po zamianie trójki z czwórką

	1	2	3	4	5
1	X	650	200	0	0
2	650	X	450	400	0
3	200	450	X	350	300
4	0	400	350	x	150
5	0	0	300	150	x

	1	2	3	4	5
1	X	4	1,5	2,5	3,5
2	4	X	2,5	1,5	3,5
3	1,5	2,5	X	3	2
4	2,5	1,5	3	x	5
5	3,5	3,5	2	5	x

∆Q (1,2)=-150 ∆Q(3,5)=-750 ∆Q(4,5)=-1250 //sytuacja jest optymalna