IN PYTHON- Please use BEST FIRST ALGORITHM to find the shortest path. Below are the two text files.

Programming details:

Youre given 2 data files.

The first is a list of all of the cities we know aboutmostly small towns in southern Kansas

and the latitude and longitude of each. For this program, were not interested in how much closer one town is than another, only finding which one is closer. Therefore we can take the coordinates as points in the XY plane and use the standard Euclidean distance formula. Names have been tweaked so that city names consisting of more than one word have an underscore rather than a space between the words (South_Haven rather than South Haven), to simplify input.

A file listing, for each town, towns that are adjacent to it. This file is line-oriented. The first town on the line is the town of interest, and the remaining towns (the number is variable) are adjacent to the first (not necessarily each other). Note that this file (being hand-constructed late at night) is not entirely complete. Towns should appear on each others adjacency list, since adjacency is symmetric: If A is adjacent to B, then B is adjacent to A. This may not be listed properly in all cases. That is, its possible A is listed as adjacent to B, C, and D, and D as adjacent to E, F, and Q; obviously it should also be adjacent to A. Take this into account when setting up your programs data structures. If adjacency is listed in either direction, it should be considered present in both directions.

Ask the user for their starting and ending towns, making sure theyre both towns in the database. Use either best-first or A* search to find a route to the destination, if one exists; print the route you find in order, from origin to destination. You might be interested in looking at a map and see how the route your program finds compares with reality. Note that your database is very limited, and I left out a lot of roads and routes. Also, all were looking at is adjacency, not distance between adjacent cities. If you put into the database that Topeka is adjacent to Denver, its going to find a route between them very quickly, and say its only one step. On the other hand, a real mapping application often gives directions such as get onto I-70, and go west until you reach the I-225 exit at Aurora, Colorado. Its only one step, but its a large one.

----------------------------------------------

Adjacencies.txt

Anthony Bluff_City Kiowa Attica Harper Attica Medicine_Lodge Augusta Winfield Andover Leon Wichita Caldwell South_Haven Bluff_City Mayfield El_Dorado Towanda Andover Augusta Emporia Florence McPherson Hillsboro El_Dorado Greensburg Coldwater Pratt Harper Anthony Argonia Rago Hutchinson Newton Haven Junction_City Abilene Marion Manhattan Topeka Kingman Cheney Pratt Hutchinson Marion McPherson Newton Emporia Mayfield Wellington Caldwell Argonia McPherson Salina Lyons Hillsboro Medicine_Lodge Attica Kiowa Coldwater Newton McPherson Hutchinson Florence Rago Viola Sawyer Salina Abilene Hays Sawyer Pratt Zenda Wellington Oxford Mayfield Mulvane South_Haven Wichita Derby Clearwater Cheney Mulvane Andover Newton El_Dorado

---------------------------

coordinates.txt

Abilene 38.9220277 -97.2666667 Andover 37.6868403 -97.1657752 Anthony 37.1575168 -98.0728946 Argonia 37.2670166 -97.7726807 Attica 37.2421271 -98.2351967 Augusta 37.6913277 -97.0537108 Bluff_City 37.0760844 -97.8793212 Caldwell 37.0346731 -97.6179436 Cheney 37.632882 -97.789442 Clearwater 37.5166968 -97.5325458 Coldwater 37.2574937 -99.3549149 Derby 37.5517122 -97.2867892 El_Dorado 37.8098997 -96.8943313 Emporia 38.3792991 -96.2615044 Florence 38.2434672 -96.9378672 Greensburg 37.6050677 -99.3005641 Harper 37.2852232 -98.0368352 Haven 37.9020486 -97.7926952 Hillsboro 38.3494571 -97.2156415 Hutchinson 38.0572062 -97.9414547 Junction_City 39.0379342 -96.8799338 Kingman 37.6480942 -98.1693967 Kiowa 37.0190996 -98.4940572 Leon 37.6892622 -96.7916587 Lyons 38.3477177 -98.22167 Manhattan 39.1682049 -96.6901159 Marion 38.3589767 -97.0267385 Mayfield 37.2618658 -97.5508871 McPherson 38.3704302 -97.6917722 Medicine_Lodge 37.2855616 -98.5888462 Mulvane 37.4868677 -97.2575929 Newton 38.0353742 -97.4239353 Oxford 37.2734026 -97.1777267 Pratt 37.6753423 -98.7769217 Rago 37.4527946 -98.0905053 Salina 38.8254325 -97.702327 Sawyer 37.4972558 -98.6880621 South_Haven 7.0497874 -97.4052061 Topeka 39.0130335 -95.7782425 Towanda 37.7971427 -97.0063152 Viola 37.4827584 -97.6496081 Wellington 37.2691963 -97.5199806 Wichita 37.6645257 -97.5841207 Winfield 37.2844228 -96.999848 Zenda 37.4447194 -98.2849356