write the C$++$ code for this program please. the optimal path is the one which has the shortest travel time. You will be implementing the following four search algorithms: Breadth$-$First Search $($BFS$),$ Depth$-$First Search $($DFS$),$ Uniform Cost Search $($UCS$),$ and A$*$ Search. Your program will read an input.txt file. The input.txt file will specify one of the four searching algorithms, as well as starting and goal locations. In addition, the input.txt file will contain live traffic information, which is a list of current traveling times $($in minutes$)$ between different locations. For example, suppose the starting location is your home and the destination is Staples Center. An example of live traffic data is as follows: Home CA$73/$NewportCoastDr $5$ CA$73/$NewportCoastDr I$405/$CA$7310$ I$405/$CA$73$ I$110/$I$40525$ I$110/$I$405$ I$10/$I$11020$ I$10/$I$110$ I$110/$I$40530$ I$10/$I$110$ I$10/$I$4059$ I$105/$I$110$ I$10/$I$1107$ I$10/$I$110$ StaplesCenter $3$ Here, each line indicates the current traveling time between two locations. For example, line $3$ indicates that it takes $25$ minutes to go from I$405/$CA$73$ to I$110/$I$405.$ Note that the location can be an intersection $($such as I$405/$CA$73).$ Traveling time may not be the same for both directions. For example, I$110/$I$405$ I$10/$I$11020$ indicates that it takes $20$ minutes to travel from I$110/$I$405$ to I$10/$I$110,$ but I$10/$I$110$ I$110/$I$40530$ indicates that it takes $30$ minutes in the other direction. Beside the live traffic information, you also have an idea of how long it takes on a traffic$-$free Sunday from each location to your goal location. Hence, the input.txt file will also contain the Sunday traffic estimate of traveling time from each location listed in the file to your destination. For the example above, the Sunday traffic data may look like this: Home $55$ CA$73/$NewportCoastDr $50$ I$405/$CA$7340$ I$110/$I$40528$ I$10/$I$1108$ I$10/$I$40539$ I$105/$I$11023$ StaplesCenter $0$ Your program should write, in an output.txt file, the list of locations traveled over in your solution path $($including the starting and goal locations$)$ and the accumulated time from start to each location, in order of travel. The following is an example of output.txt: Home $0$ CA$73/$NewportCoastDr $5$ I$405/$CA$7315$ I$110/$I$40540$ I$10/$I$11060$ StaplesCenter $63$ The full specification of input.txt and output.txt is shown on the next page. Full specification for input.txt: $<...$ LIVE TRAFFIC LINES $...><...$ SUNDAY TRAFFIC LINES $...>$ where: is the algorithm to use and will be one of the following: $$BFS$,$DFS$,$UCS$,$A$*$ is a string with the name of the start location $($e$.$g$.,$Home$)$ is a string with the name of the goal location $($e$.$g$.,$StaplesCenter$)$ is the number of lines of live traffic information that follow. $<...$ LIVE TRAFFIC LINES $...>$ are lines of live traffic information in the format previously described, i$.$e$.,$ is the number of lines of Sunday traffic estimates that follow. $<...$ SUNDAY TRAFFIC LINES $...>$ are lines of Sunday traffic information in the format previously described, i$.$e$.,$ Full specification for output.txt: Any number of lines with the following format for each line: $****$Important guidelines on next two pages$****$ Guidelines: Your program should not require any command$-$line argument. It should read a text file called $$input$.$txt$$ in the current directory that contains a problem definition. It should write a file called $$output$.$txt$($in the current directory$)$ with your solution. Format for input.txt and output.txt is specified in the previous page. Samples of input and output are shown on the last few pages of this assignment description. The goal of the samples is to check that you can correctly parse the problem definitions, and generate a correctly formatted output. Your output should match the specified format exactly. It should not be assumed that if your program works on the samples it will work on all test cases.