java or python

Algorithms, you recognize that this is an application for Dijkstra's shortest path algorithm. To prepare for your proposal, you decide to implement it on your computer. The requirements are listed below. Note that marks are also awarded for presentation of your program output. Requirement 1 - Representation of the map in Figure 1 Represent the city-distance information shown in the map in Figure 1 with a weighted graph using adjacency matrix or link-list. Sembawang Woodlands 5 6 6 9 B 4 6 6 14 Bukit 6 5 11 Punggol Mandal 3 Nee Soon Choa Chu Kang 11/15 16 6 Bukit 16 Ang Mo Kio 8 6 16 Changi Ranjang 5/ 7 6 18 8 Serangoon 12 5 15 oper 6 22 11 Thomson 16 18 Tampines Batak 15 Bukit 6 19 5 Fimah 5 das 5 9 10 Jurong 19 10 Nga Payoh 16 Bedok 9 5 Clement Marina Bay Queenstown 16 Pasir 5 Panjang Outram 10 8 22 16 257 8 Vo 6 6 Sonusa Figure 1 Requirement 2 - Implementation Write an interactive program that given the start and destination cities, will determine the shortest route between them and its total distance. It is all right to have 0 distance; i.e., start and end at the same city. You can assume that the roads are all bi-direction; i.e., vehicle can travel in both directions. The output of your program may look something similar as follow: Start from: Changi To: Choa Chu Kang Path: Changi -> Toa Payoh -> Bukit Timah -> Bukit Batok -> Choa Chu Kang Total distance: 39 Km. Requirement 3 Test run Test your program by determining the following routes: Changi to Choa Chu Kang Bedok to Bukit Batok Marina Bay to Woodlands Sembawang to Bukit Timah . Upper Thomson to Outram Bukit Batok to Tampines Requirement 4 - Program Complexity Derive the program running time complexity of your algorithm using Big-O notation. State clearly how you arrive at the Big-O notation. Partial marks will be awarded only for stating without showing the work in arriving at your conclusion. 9 Mandai 8 8 8 2 8 8 8 8 8 8 8 7 8 8 8 8 6 8 8 8 8 8 8 do V og Jurong 3 8 8 8 Choa Chu Kang 8 8 6 + 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 4 8 = 6. Changi 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 8 8 8 8 8 U I Clementi 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 G 4 Bukit Timah 8 / 8 0 0 0 8 2 8 8 8 8 8 8 8 8 8 8 8 = 8 F 3 Bukit Panjang 16 co 7 8 8 8 + 8 2 8 8 8 8 8 8 8 8 8 8 8 = Bukit Batok 18 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 M 8 8 8 C 0 Ang Mo Kio 8 894 8 8 8 8 8 8 8 6 8 8 8 8 8 8 6 8 8 8 8 ... From B Index Ang Mo Kio Bedok Timah Bukit Batok Bukit Panjang Clementi Changi Choa Chu Kang Jurong Mandai Marina Bay Nee Soon Outram Pasir Panjang Punggol Queenstown Sembawang Sentosa Serangoon Tampines Toa Payoh Tuas Upper Thomsor Woodlands Bukit To . Index 0 1 2 3 4 5 6 7 8 9 10. 11 12 13 14 15 16 17 18 19 20 21 22 23 DO DO DO DO DO DO DO 5 DO DO DO DO 9 DO DO DO 9 DO 8 DO DO 10 DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO 6 DO DO 15 DO DO 6 DO 8 DO 10 6 12 DO DO DO DO DO DO DO DO DO DO DO 15 6 DO 8 DO 12 DO DO DO DO 8 DO DO DO DO DO DO DO DO DO DO DO DO 10 DO 8 6 DO DO 5 DO DO DO DO DO DO DO DO DO DO DO 5 DO DO 10 DO 9 DO DO 10 DO DO DO 9 5 DO DO DO DO DO DO DO 8 DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO 8 6 6 5 DO DO DO 8 DO DO DO DO DO DO 2 9 DO DO DO DO DO 5 DO DO DO DO DO DO DO DO 10 DO DO DO DO DO DO DO 2 2 DO 8 DO DO DO DO DO DO 9 DO DO DO DO 3 DO DO DO DO DO DO DO DO DO DO DO DO DO DO 19 15 11 DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO 18 5 16 DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO 5 DO 7 DO DO DO DO 11 DO 10 DO DO DO DO 6 DO DO DO DO DO 11 14 DO DO DO DO DO DO DO DO DO DO 16 DO DO 16 DO DO DO DO DO DO DO DO DO DO 13 5 DO DO DO 16 16 DO DO DO DO 9 DO DO DO DO DO DO 6 DO Woodlands 23 Z 16 5 Upper Thomson 22 Y Y Tuas 21 Toa Payoh 20 W Tampines 19 V Serangoon 18 U Sentosa 17 Sembawang 16 Queenstown 15 R Punggol 14 Q Pasir Panjang 13 Outram 12 Nee Soon 11 Marina Bay 10 I S P O N M Algorithms, you recognize that this is an application for Dijkstra's shortest path algorithm. To prepare for your proposal, you decide to implement it on your computer. The requirements are listed below. Note that marks are also awarded for presentation of your program output. Requirement 1 - Representation of the map in Figure 1 Represent the city-distance information shown in the map in Figure 1 with a weighted graph using adjacency matrix or link-list. Sembawang Woodlands 5 6 6 9 B 4 6 6 14 Bukit 6 5 11 Punggol Mandal 3 Nee Soon Choa Chu Kang 11/15 16 6 Bukit 16 Ang Mo Kio 8 6 16 Changi Ranjang 5/ 7 6 18 8 Serangoon 12 5 15 oper 6 22 11 Thomson 16 18 Tampines Batak 15 Bukit 6 19 5 Fimah 5 das 5 9 10 Jurong 19 10 Nga Payoh 16 Bedok 9 5 Clement Marina Bay Queenstown 16 Pasir 5 Panjang Outram 10 8 22 16 257 8 Vo 6 6 Sonusa Figure 1 Requirement 2 - Implementation Write an interactive program that given the start and destination cities, will determine the shortest route between them and its total distance. It is all right to have 0 distance; i.e., start and end at the same city. You can assume that the roads are all bi-direction; i.e., vehicle can travel in both directions. The output of your program may look something similar as follow: Start from: Changi To: Choa Chu Kang Path: Changi -> Toa Payoh -> Bukit Timah -> Bukit Batok -> Choa Chu Kang Total distance: 39 Km. Requirement 3 Test run Test your program by determining the following routes: Changi to Choa Chu Kang Bedok to Bukit Batok Marina Bay to Woodlands Sembawang to Bukit Timah . Upper Thomson to Outram Bukit Batok to Tampines Requirement 4 - Program Complexity Derive the program running time complexity of your algorithm using Big-O notation. State clearly how you arrive at the Big-O notation. Partial marks will be awarded only for stating without showing the work in arriving at your conclusion. 9 Mandai 8 8 8 2 8 8 8 8 8 8 8 7 8 8 8 8 6 8 8 8 8 8 8 do V og Jurong 3 8 8 8 Choa Chu Kang 8 8 6 + 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 4 8 = 6. Changi 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 8 8 8 8 8 U I Clementi 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 G 4 Bukit Timah 8 / 8 0 0 0 8 2 8 8 8 8 8 8 8 8 8 8 8 = 8 F 3 Bukit Panjang 16 co 7 8 8 8 + 8 2 8 8 8 8 8 8 8 8 8 8 8 = Bukit Batok 18 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 M 8 8 8 C 0 Ang Mo Kio 8 894 8 8 8 8 8 8 8 6 8 8 8 8 8 8 6 8 8 8 8 ... From B Index Ang Mo Kio Bedok Timah Bukit Batok Bukit Panjang Clementi Changi Choa Chu Kang Jurong Mandai Marina Bay Nee Soon Outram Pasir Panjang Punggol Queenstown Sembawang Sentosa Serangoon Tampines Toa Payoh Tuas Upper Thomsor Woodlands Bukit To . Index 0 1 2 3 4 5 6 7 8 9 10. 11 12 13 14 15 16 17 18 19 20 21 22 23 DO DO DO DO DO DO DO 5 DO DO DO DO 9 DO DO DO 9 DO 8 DO DO 10 DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO 6 DO DO 15 DO DO 6 DO 8 DO 10 6 12 DO DO DO DO DO DO DO DO DO DO DO 15 6 DO 8 DO 12 DO DO DO DO 8 DO DO DO DO DO DO DO DO DO DO DO DO 10 DO 8 6 DO DO 5 DO DO DO DO DO DO DO DO DO DO DO 5 DO DO 10 DO 9 DO DO 10 DO DO DO 9 5 DO DO DO DO DO DO DO 8 DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO 8 6 6 5 DO DO DO 8 DO DO DO DO DO DO 2 9 DO DO DO DO DO 5 DO DO DO DO DO DO DO DO 10 DO DO DO DO DO DO DO 2 2 DO 8 DO DO DO DO DO DO 9 DO DO DO DO 3 DO DO DO DO DO DO DO DO DO DO DO DO DO DO 19 15 11 DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO 18 5 16 DO DO DO DO DO DO DO DO DO DO DO DO DO DO DO 5 DO 7 DO DO DO DO 11 DO 10 DO DO DO DO 6 DO DO DO DO DO 11 14 DO DO DO DO DO DO DO DO DO DO 16 DO DO 16 DO DO DO DO DO DO DO DO DO DO 13 5 DO DO DO 16 16 DO DO DO DO 9 DO DO DO DO DO DO 6 DO Woodlands 23 Z 16 5 Upper Thomson 22 Y Y Tuas 21 Toa Payoh 20 W Tampines 19 V Serangoon 18 U Sentosa 17 Sembawang 16 Queenstown 15 R Punggol 14 Q Pasir Panjang 13 Outram 12 Nee Soon 11 Marina Bay 10 I S P O N M