A well documents and well structured Java program that will utilize a best$-$first branch$-$and$-$bound strategy to solve the traveling salesman problem. You must also use a priority queue to handle your best first traversal.

Input will be a value designating the number of nodes and followed by a adjacency matrix separated by spaces. If no path exist $-1$ will be placed in the matrix.

Output will be the Hamiltonian path followed by the total cost of the path.

Example input: $($P$4$input.txt$)$

$7$

$01210-1-1-112$

$120812-1-1-1$

$1080113-19$

$-1121101110-1$

$-1-1311067$

$-1-1-110609$

$12-19-1790$

$$

Expected output$$

Path $=[1],,$ Bound $=47$

Path $=[1,2],,$ Bound $=49$

Path $=[1,3],,$ Bound $=54$

Path $=[1,7],,$ Bound $=49$

$-$

$-$

$-$

$-$

$-$

$-$ find path and bound of each node by best$-$first branch$-$and$-$bound strategy as shown in figure. Make sure bound is same as shown in figure while giving output.

optimizedPath$-1,2,4,6,7,5,3,1$

Total cost$-63$