Travelling Salesman Problem (Algorithm)

$\text{TSP}(G)$:

1. Let $D^{-}\leftarrow 0$.
2. Let $D^{+}\leftarrow \text{total weight of all edges of }G$
3. While $(D^{+}-D^{-})<\text{ shortest edge of }G$:
   1. Let $\text{mid }\leftarrow (D^{+}+D^{-})/2$
   2. If $\text{TSP-DEC}(G,m)=H$:
      1. Let $D^{+}\leftarrow \text{mid}$
   3. Else:
      1. Let $D^{-}\leftarrow \text{mid}$
4. Return route $H$ of length $\text{mid}$

$\text{TSP-DEC}(G,D)$:

1. Use algorithm to find optimal route $H$
2. If length of $H\le D$:
   1. Return route $H$
3. Else:
   1. Return $\perp$