Editing Travelling salesman problem (section)

====Conversion to symmetric====
Solving an asymmetric TSP graph can be somewhat complex. The following is a 3×3 matrix containing all possible path weights between the nodes ''A'', ''B'' and ''C''. One option is to turn an asymmetric matrix of size ''N'' into a symmetric matrix of size 2''N''.<ref>{{cite journal | last1 = Jonker | first1 = Roy | last2 = Volgenant | first2 = Ton | title = Transforming asymmetric into symmetric traveling salesman problems | journal = [[Operations Research Letters]] | volume = 2 | issue = 161–163| page = 1983 | doi = 10.1016/0167-6377(83)90048-2 | year = 1983 }}</ref>

:{| class="wikitable"
|- style="text-align:center;"
|+ Asymmetric path weights
! !! ''A'' !! ''B'' !! ''C''
|- style="text-align:center;"
! ''A''
| || 1 || 2
|- style="text-align:center;"
! ''B''
| 6 || || 3
|- style="text-align:center;"
! ''C''
| 5 || 4 ||
|}

To double the size, each of the nodes in the graph is duplicated, creating a second ''ghost node'', linked to the original node with a "ghost" edge of very low (possibly negative) weight, here denoted −''w''. (Alternatively, the ghost edges have weight 0, and weight w is added to all other edges.) The original 3×3 matrix shown above is visible in the bottom left and the transpose of the original in the top-right. Both copies of the matrix have had their diagonals replaced by the low-cost hop paths, represented by −''w''. In the new graph, no edge directly links original nodes and no edge directly links ghost nodes.

:{| class="wikitable"
|- style="text-align:center;" class="wikitable"
|+ Symmetric path weights
! !! ''A'' !! ''B'' !! ''C'' !! ''A&prime;'' !! ''B&prime;'' !! ''C&prime;''
|- style="text-align:center;"
! ''A''
| || || || −''w'' || 6 || 5
|- style="text-align:center;"
! ''B''
| || || || 1 || −''w'' || 4
|- style="text-align:center;"
! ''C''
| || || || 2 || 3 || −''w''
|- style="text-align:center;"
! ''A&prime;''
| −''w'' || 1 || 2 || || ||
|- style="text-align:center;"
! ''B&prime;''
| 6 || −''w'' || 3 || || ||
|- style="text-align:center;"
! ''C&prime;''
| 5 || 4 || −''w'' || || ||
|}

The weight −''w'' of the "ghost" edges linking the ghost nodes to the corresponding original nodes must be low enough to ensure that all ghost edges must belong to any optimal symmetric TSP solution on the new graph (''w'' = 0 is not always low enough). As a consequence, in the optimal symmetric tour, each original node appears next to its ghost node (e.g. a possible path is <math>\scriptstyle{A \to A' \to C \to C' \to B \to B' \to A}</math>), and by merging the original and ghost nodes again we get an (optimal) solution of the original asymmetric problem (in our example, <math>\scriptstyle{A \to C \to B \to A}</math>).