Please reference this program $($deliverable B$)$ to answer the question:

import java.io$.*$;

import java.util.$*$;

public class DeliverableB $\{$

File inputFile;

File outputFile;

PrintWriter output;

Graph g;

$//$ initialize the input file and graph

public DeliverableB $($File in$,$ Graph gr$)\{$

inputFile $=$ in;

g $=$ gr;

$//$ setting up the output file

String inputFileName $=$ inputFile.toString$()$;

String baseFileName $=$ inputFileName.substring$(0,$ inputFileName.length$()-4)$;

String outputFileName $=$ baseFileName.concat$("\_$bitoni$\_$out.txt$")$;

outputFile $=$ new File$($outputFileName$)$;

$//$ if the output file already exists, delete it

if$($outputFile$.$exists$())\{$

outputFile.delete$()$;

$\}$

try $\{$

output $=$ new PrintWriter$($outputFile$)$;

$\}$

catch $($Exception x$)\{$

System.err.format $("$Exception: $\%$s$\%$n $",$ x$)$;

System.exit$(0)$;

$\}$

$//$sort the cities based on values $($longitude $/$ latitude$)$

Collections.sort$($g$.$getNodeList$(),$ new Comparator$()\{$

@Override

public int compare$($Node n$1,$ Node n$2)\{$

return Double.compare$($n$1.$getVal$(),$ n$2.$getVal$())$;

$\}$

$\})$;

$//$ calculate the shortest bitonic tour

int numCities $=$ g$.$getNodeList$().$size$()$;

$//$ distance matrix

double$[][]$ distance $=$ new double$[$numCities$][$numCities$]$;

$//$table for dp

double$[][]$ dp $=$ new double $[$numCities$][$numCities$]$;

int$[][]$ path $=$ new int$[$numCities$][$numCities$]$;

$//$ intialize the distance matrix

for $($int i $=0$; i $$ numCities; i$++)\{$

for$($int j $=1+$ i; j $$ numCities; i$++)\{$

distance$[$i$][$j$]=$ g$.$getNodeList$().$get$($i$).$findEdgeTo$($g$.$getNodeList$())$;

distance$[$j$][$i$]=$ distance$[$i$][$j$]$;

$\}$

$\}$

$//$initializing dp table

for $($int i $=0$; i $$ numCities; i$++)\{$

for $($int j $=0$; j $$ numCities; j$++)\{$

dp$[$i$][$j$]=$ Double.POSITIVE$\_$INFINITY;

$\}$

$\}$

$//$begin from the first city, set distance to $0$

dp$[0][0]=0$;

$//$ fill out DP table with bitonic tour algorithm

for $($int j $=1$; j $$ numCities; j$++)\{$

for $($int i $=0$; i $$ j; i$++)\{$

if $($i $==$ j $-1)\{$

for $($int k $=0$; k $$ i; k$++)\{$

if $($dp$[$k$][$i$]+$ distance$[$k$][$j$]$ dp$[$i$][$j$])\{$

dp$[$i$][$j$]=$ dp$[$k$][$i$]+$ distance$[$k$][$j$]$;

$//$ add previous city to the path

path$[$i$][$j$]=$ k;

$\}$

$\}$

$\}$ else $\{$

dp$[$i$][$j$]=$ dp$[$i$][$j $-1]+$ distance$[$j $-1][$j$]$;

$//$add current city to the path

path$[$i$][$j$]=$ i;

$\}$

$\}$

$\}$

$//$ the trip from the last city to origin

double minTourLength $=$ dp$[$numCities $-2][$numCities $-1]+$ distance$[$numCities $-2][$numCities $-1]$;

int endCity$1=$ numCities $-2$;

int endCity$2=$ numCities $-1$;

$//$output the total distance travelled of the bitonic tour

System.out.println$("$Shortest bitonic tour has distance $"+$ minTourLength$)$;

List tour $=$ new ArrayList;

reconstructPath$($path$,$ endCity$1,$ endCity$2,$ g$,$ tour$)$;

$//$output tour info

System.out.print$("$Tour is $")$;

for $($Node node : tour$)\{$

System.out.print$($node$.$getAbbrev$()+"")$;

output.print$($node$.$getAbrrev$()+"")$;

$\}$

$\}$

private void reconstructPath$($int$[][]$ path, int i$,$ int j$,$ Graph g$,$ List tour$)\{$

if$($i $!=$ j $-1)\{$

reconstructPath$($path$,$ path$[$i$][$j$],$ i$,$ g$,$ tour$)$;

$\}$

$//$ add cities i and j to the path

tour.add$($g$.$getNodeList$().$get$($i$))$;

tour.add$($g$.$getNodeList$().$get$($j$))$;

$\}$

$\}$

Start with your $($ideally working$)$ submission of Deliverable B$.$ Read a file of the name $$F$[]$c$.$txt$.$ This is a file of distances between cities in which the value of each city is either

$$S$$ Starting city

$$G$$ Goal city

$$~$$ neither starting nor goal city

Perform a depth$-$first branch$-$and$-$bound search, beginning with the starting city, to find the nearest goal city.$$ Report the nearest goal city, and the distance to it$,$ in the format listed below.$[1]$

Algorithm:

The depth$-$first$-$search algorithm is described in the powerpoint slides and video $$Search III $$ DFS$,$ and its use for branch$-$and$-$bound is described in $$Search VII $$ Bounded DFS $+$ comments$.$ This is consistent $($I think $)$ with Chapter $20$ of the CLFS textbook and Chapter $3$ of the P&M textbook.$$ The details of the algorithm are the same as they were for the Homework on this topic:

$$ Measure the depth bound in terms of total distance to the goal node as measured by edge lengths.

$$ When choosing which node to visit next, visit the nearest unvisited node.$$ Break ties alphabetically.$$

Output:

The input will be a table of distances representing a graph.

Example F$1$c:

Source is B$,$ goal is E$.$ I may test with this file, with same or different source node and$/$or goal node$($s$).$