Solve in python
Romania with step costs in km PROBLEM SCENARIO On holiday, a flight currently wants to travel to Bucharest from Arad. But there is no direct way to Bucharest from Arad. However, the cities are connected with each other like a graph. The distance between the connected cities are given. The flight wants to travel through the most optimal way. To find the optimal path to travel, another information is provided: the straight line distance between any city and the final destination (Bucharest). Now help the flight to determine the most optimal value with A search for the route Arad to Bucharest. You have to use the straight line distance as the heuristic value for the cities. \begin{tabular}{l|l|l|l} \hline City & Heuristic value & City & Heuristic value \\ \hline Arad & 366 & Mehadia & 241 \\ \hline Bucharest & 0 & Neamt & 234 \\ \hline Craiova & 160 & Oradea & 380 \\ \hline Eforie & 161 & Pitesti & 100 \\ \hline Fagaras & 176 & Rimnicu Vilcea & 193 \\ \hline Dobreta & 242 & Timisoara & 329 \\ \hline Hirsova & 151 & Urziceni & 80 \\ \hline lasi & 226 & Vaslui & 199 \\ \hline Lugoj & 244 & Zerind & 374 \\ \hline For si & & & \\ \hline \end{tabular} For simplicity assume these notations \begin{tabular}{l|l|l|l|} \hline Arad & A & Neamt & F \\ \hline Bucharest & Z & Oradea & B \\ \hline Craiova & S & Pitesti & P \\ \hline Eforie & T & Rimnicu Vilcea & R \\ \hline Fagaras & O & Timisoara & C \\ \hline Dobreta & V & Urziceni & D \\ \hline Hirsova & N & Vaslui & H \\ \hline lasi & Q & Zerind & E \\ \hline Lugoj & G & & \\ \hline Mehadia & L & & \\ \hline \end{tabular} INPUTS Your txt file should take each node followed by each destination it can reach and their corresponding distance and heuristics. You are to read the file then ask the user to input the starting and the destination point. OUTPUTS The output will contain the total distance from the starting point to the destination followed by printing the nodes it followed to calculate the distance. SAMPLE INPUT In the text file: Arad 366 Zerind 75 Timisoara 118 Sibiu 140 Craiova 160 Dobreta 120 RimnicuVillcea 146 Pitesti 138 Eforie 161 Hirsova 86 Fagaras 176 Sibiu 99 Bucharest 211 Giurgiu 77 Bucharest 90 Mehadia 241 Lugoj 70 Dobreta 75 Neamt 234 lasi 87 Sibiu 253 Oradea 151 Arad 140 RimnicuVilcea 80 Fagaras 99 Oradea 380 Zerind 71 Sibiu 151 Pitesti 100 RimnicuVilcea 97 Craiova 138 Bucharest 101 RimnicuVilcea 193 Sibiu 80 Craiova 146 Pitesti 97 Dobreta 242 Mehadia 75 Craiova 120 Hirsova 151 Urziceni 98 Eforie 86 lasi 226 Vaslui 92 Neamt 87 Lugoj 244 Timisoara 111 Mehadia 70 Timisoara 329 Arad 118 Lugoj 111 Urziceni 80 Bucharest 85 Hirsova 98 Vaslui 142 Vaslui 199 Urziceni 142 lasi 92 Zerind 374 Oradea 71 Arad 75 Bucharest 0 Fagaras 211 Pitesti 101 Giurgiu 90 Urziceni 85 The text file is arranged as follows: Each line starts with a node followed by the heuristic of that node Then the neighboring nodes and the distance from the parent node is given as a pair All neighboring city-distance pairs are listed after the heuristic. For example, the text file starts with Arad which has a heuristic of 366 . It is the parent node to Zerind, Sibiu and Timisoara which are 75,140 and 118km away from Arad. Notice that since Bucharest is the End node which is why it has a heuristic of 0 . In console: Start node: Arad Destination: Bucharest Sample output Path: Arad Sibiu Rimnicu > Pitesti Bucharest Total distance: 418km If there is no path found from the Start node to the End node, simply print "NO PATH FOUND" Romania with step costs in km PROBLEM SCENARIO On holiday, a flight currently wants to travel to Bucharest from Arad. But there is no direct way to Bucharest from Arad. However, the cities are connected with each other like a graph. The distance between the connected cities are given. The flight wants to travel through the most optimal way. To find the optimal path to travel, another information is provided: the straight line distance between any city and the final destination (Bucharest). Now help the flight to determine the most optimal value with A search for the route Arad to Bucharest. You have to use the straight line distance as the heuristic value for the cities. \begin{tabular}{l|l|l|l} \hline City & Heuristic value & City & Heuristic value \\ \hline Arad & 366 & Mehadia & 241 \\ \hline Bucharest & 0 & Neamt & 234 \\ \hline Craiova & 160 & Oradea & 380 \\ \hline Eforie & 161 & Pitesti & 100 \\ \hline Fagaras & 176 & Rimnicu Vilcea & 193 \\ \hline Dobreta & 242 & Timisoara & 329 \\ \hline Hirsova & 151 & Urziceni & 80 \\ \hline lasi & 226 & Vaslui & 199 \\ \hline Lugoj & 244 & Zerind & 374 \\ \hline For si & & & \\ \hline \end{tabular} For simplicity assume these notations \begin{tabular}{l|l|l|l|} \hline Arad & A & Neamt & F \\ \hline Bucharest & Z & Oradea & B \\ \hline Craiova & S & Pitesti & P \\ \hline Eforie & T & Rimnicu Vilcea & R \\ \hline Fagaras & O & Timisoara & C \\ \hline Dobreta & V & Urziceni & D \\ \hline Hirsova & N & Vaslui & H \\ \hline lasi & Q & Zerind & E \\ \hline Lugoj & G & & \\ \hline Mehadia & L & & \\ \hline \end{tabular} INPUTS Your txt file should take each node followed by each destination it can reach and their corresponding distance and heuristics. You are to read the file then ask the user to input the starting and the destination point. OUTPUTS The output will contain the total distance from the starting point to the destination followed by printing the nodes it followed to calculate the distance. SAMPLE INPUT In the text file: Arad 366 Zerind 75 Timisoara 118 Sibiu 140 Craiova 160 Dobreta 120 RimnicuVillcea 146 Pitesti 138 Eforie 161 Hirsova 86 Fagaras 176 Sibiu 99 Bucharest 211 Giurgiu 77 Bucharest 90 Mehadia 241 Lugoj 70 Dobreta 75 Neamt 234 lasi 87 Sibiu 253 Oradea 151 Arad 140 RimnicuVilcea 80 Fagaras 99 Oradea 380 Zerind 71 Sibiu 151 Pitesti 100 RimnicuVilcea 97 Craiova 138 Bucharest 101 RimnicuVilcea 193 Sibiu 80 Craiova 146 Pitesti 97 Dobreta 242 Mehadia 75 Craiova 120 Hirsova 151 Urziceni 98 Eforie 86 lasi 226 Vaslui 92 Neamt 87 Lugoj 244 Timisoara 111 Mehadia 70 Timisoara 329 Arad 118 Lugoj 111 Urziceni 80 Bucharest 85 Hirsova 98 Vaslui 142 Vaslui 199 Urziceni 142 lasi 92 Zerind 374 Oradea 71 Arad 75 Bucharest 0 Fagaras 211 Pitesti 101 Giurgiu 90 Urziceni 85 The text file is arranged as follows: Each line starts with a node followed by the heuristic of that node Then the neighboring nodes and the distance from the parent node is given as a pair All neighboring city-distance pairs are listed after the heuristic. For example, the text file starts with Arad which has a heuristic of 366 . It is the parent node to Zerind, Sibiu and Timisoara which are 75,140 and 118km away from Arad. Notice that since Bucharest is the End node which is why it has a heuristic of 0 . In console: Start node: Arad Destination: Bucharest Sample output Path: Arad Sibiu Rimnicu > Pitesti Bucharest Total distance: 418km If there is no path found from the Start node to the End node, simply print "NO PATH FOUND
