Distance between Bucharest to any cities Amsterdam 2280 Copenhagen 2250 Madrid Athens 1300 Dublin 2530 Milan Barcelona 2670 Glasgow 2470 Munich Belgrade 630 Helsinki 2820 Oslo Berlin 3950 Palermo 2590 Paris 1660 Prague 1800 Lisbon Bordeaux 2100 London Budapest 900 Lyon 3300 Rome 1750 Sofia 1600 Stockholm 2870 Vienna 1280 Warsaw 2970 1490 1140 390 2890 1150 946 Part III: Long answer problems For a given map with cities from Europe and distances between them, find the shortest path from Paris to Bucharest knowing that the direct distances between the cities are in the table. Use the following methods to address it and show your steps in search trees. (1) DFS (2) BFS (3) UCS (4) A* Map of cities in Europe Lisbon Glasgow C Dublin London Bordeaux Madrid Amsterdam Lygg Paris O Oslo Barcelona Munich Copenhagen Berlin Olso - Helsinki: 970 Rome: Milan: Helsinki - Stockholm: 400 Milan - Budapest: Oslo - Stockholm: 570 Vienna - Budapest: Stockholm - Copenhagen: 522 Vienna - Munich: Copenhagen - Warsaw: 668 Prague - Vienna: Warsaw - Bucharest: 946 Prague - Berlin: Bucharest - Athens: 1300 Berlin Copenhagen: Budapest - Bucharest: 900 Berlin - Amsterdam: Budapest - Belgrade: 316 Munich -Lyon: Belgrade - Sofia: 330 Lyon-Paris: Rome - Palermo: 1043 Lyon - Bordeaux: Palermo - Athens: 907 Stockholm Prague Theona Milan Rome Palermo City distances Helsinki Warsaw Budapest Belgrade Bucharest Sofig Athens 681 Madrid- Barcelona: 789 Madrid - Lisbon: 217 Lisbon - London: 458 Barcelona - Lyon: 312 Paris - London: 354 London - Dublin: 743 London - Glasgow: 648 Glasgow - Amsterdam: 753 Budapest - Prague: 481 Barcelona - Rome: 542 Paris - Bordeaux: Glasgow - Dublin: 628 638 2210 644 414 463 667 711 443 1471 579 306