Need help in Java for this question:
(Has to be done in Djikstra's shortest path algorithm FYI)
Below is the adjacency matrix for your reference
I have also done the first requirement which requires the adjacency matrix to be coded in Java:
public class Req1 { public static void main(String[] args) { //copying all the data int[][] distance = {{-1,-1,18,16,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,-1,-1,-1,-1,6,-1,-1,-1,5,-1}, {-1,-1,-1,-1,22,-1,-1,-1,-1,-1,16,-1,16,-1,-1,-1,-1,-1,-1,5,13,-1,16,-1}, {18,-1,-1,7,5,7,-1,6,19,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,16,-1,-1}, {16,-1,7,-1,6,-1,-1,4,-1,15,-1,16,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,14,11}, {-1,22,5,6,-1,5,-1,-1,25,-1,-1,-1,-1,-1,-1,9,-1,-1,-1,-1,10,-1,11,-1}, {-1,-1,7,-1,5,-1,-1,-1,-1,-1,-1,-1,-1,7,-1,5,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,16,5,18,-1,-1,-1}, {-1,-1,6,4,-1,-1,-1,-1,22,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,15,-1,11}, {-1,-1,19,-1,25,-1,-1,22,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,19,-1,-1},//8 {-1,-1,-1,15,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,6,-1,-1,-1,-1,-1,-1,8},//9 {-1,16,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,2,-1,-1,-1,-1,-1,-1,-1,10,-1,-1,-1},//10 {6,-1,-1,16,-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,5,-1,-1,-1,-1,-1,-1,9},//11 {-1,16,-1,-1,-1,-1,-1,-1,-1,-1,2,-1,-1,-1,-1,5,-1,6,-1,-1,8,-1,-1,-1},//12 {-1,-1,-1,-1,-1,7,-1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,8,-1,-1,-1,-1,-1,-1},//13 {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,8,-1,-1,-1,-1},//14 {-1,-1,-1,-1,9,5,-1,-1,-1,-1,-1,-1,5,6,-1,-1,-1,10,-1,-1,9,-1,10,-1},//15 {-1,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,5},//16 {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,6,8,-1,10,-1,-1,-1,-1,-1,-1,-1,-1},//17 {6,-1,-1,-1,-1,-1,16,-1,-1,-1,-1,-1,-1,-1,8,-1,-1,-1,-1,12,6,-1,8,-1},//18 {-1,5,-1,-1,-1,-1,5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,12,-1,15,-1,-1,-1},//19 {-1,13,-1,-1,10,-1,18,-1,-1,-1,10,-1,8,-1,-1,9,-1,-1,6,15,-1,-1,6,-1},//20 {-1,-1,16,-1,-1,-1,-1,15,19,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},//21 {5,16,-1,14,11,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,10,-1,-1,8,-1,6,-1,-1,-1},//22 {-1,-1,-1,11,-1,-1,-1,11,-1,8,-1,9,-1,-1,-1,-1,5,-1,-1,-1,-1,-1,-1,-1}}; //Printing the header System.out.println("============================== "+ " ADJACENCY MATRIX OF SINGAPORE "+ "=============================="); // Printing the location index numbers for(int i=0;i
The output for requirement 2 and 3 should look something like this:
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; ie., start and end at the same city. You can assume that the roads are all bi-direction; ie., 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 determing 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 15 1 Bedok 2 Bukit Batok 18 Bukit Panjang 16 4 Bukit Timah 5 Clementi 6 Changi Chn Chu Vang 8 Jurong 9 Mandai 10 Marina Bay 11 Nee Soon 6 12 Outram 13 Pasir Panjang 14 Punggol 16 Sembawang 17 Sentosa 18 Serangoon 6 19 Tampines 20 Toa Payoh 21 Tuas 23 Woodlande Queenstown Index 0 1 2 2 22 Upper Thomson 5 16 16 16 5 13 7 22 5 6 7 7 19 16 6 4 15 16 11 7 5 7 14 11 22 6 5 25 10 9 5 5 7 4 5 6 7 16 5 18 4 22 11 6 19 15 19 25 22 15 3 6 8 16 2 10 Index 0 To | From Ang Mo Kio Ang Mo Kio Bedok Bukit Batok 18 Bukit Panjang 16 Bukit Timah Clementi Changi Cho thu Cang Jurong Mandal Marina Bay Nec Soon 6 Outram Pasir Panjang Punggol Queenstown Sembawang Sentosa Serangoon 6 Tampines Toa Payoh Tues Upper Thomson 5 Woodlande 16 5 9 16 2 6 7 5 6 6 8 9 5 5 6 10 9 10 6 5 10 11 12 13 14 15 16 17 18 19 20 21 22 23 5 6 8 10 8 12 16 5 18 6 15 5 13 12 6 10 10 8 9 15 6 16 15 19 16 11 10 6 14 11 11 8 9 5 [1] DISPLAY CITY-DISTANCE INFORMATION MATRIX [2] SHORTEST DISTANCE BETWEEN TWO CITIES [3] ADJACENT CITY DISTANCE FROM A CITY [0] Quit Enter Choice --> 2 0 ANG MO KIO 1 BEDOK 2 BUKIT BATOK 3 BUKIT PANJANG 4 BUKIT TIMAH 5 CHANGI 6 CHOA CHU KANG CLEMENTI 18 SERANGOON 19 TAMPINES 20 TOA PAYOH 21 TUAS 22 UPPER THOMSON 23 WOODLANDS Select a integer starting point: 0 Select a integer end point: 9 Start from: ANG MO KIO To: MANDAI Path: ANG MO KIO -> NEE SOON -> MANDAI Total Distance: 9km 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; ie., start and end at the same city. You can assume that the roads are all bi-direction; ie., 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 determing 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 15 1 Bedok 2 Bukit Batok 18 Bukit Panjang 16 4 Bukit Timah 5 Clementi 6 Changi Chn Chu Vang 8 Jurong 9 Mandai 10 Marina Bay 11 Nee Soon 6 12 Outram 13 Pasir Panjang 14 Punggol 16 Sembawang 17 Sentosa 18 Serangoon 6 19 Tampines 20 Toa Payoh 21 Tuas 23 Woodlande Queenstown Index 0 1 2 2 22 Upper Thomson 5 16 16 16 5 13 7 22 5 6 7 7 19 16 6 4 15 16 11 7 5 7 14 11 22 6 5 25 10 9 5 5 7 4 5 6 7 16 5 18 4 22 11 6 19 15 19 25 22 15 3 6 8 16 2 10 Index 0 To | From Ang Mo Kio Ang Mo Kio Bedok Bukit Batok 18 Bukit Panjang 16 Bukit Timah Clementi Changi Cho thu Cang Jurong Mandal Marina Bay Nec Soon 6 Outram Pasir Panjang Punggol Queenstown Sembawang Sentosa Serangoon 6 Tampines Toa Payoh Tues Upper Thomson 5 Woodlande 16 5 9 16 2 6 7 5 6 6 8 9 5 5 6 10 9 10 6 5 10 11 12 13 14 15 16 17 18 19 20 21 22 23 5 6 8 10 8 12 16 5 18 6 15 5 13 12 6 10 10 8 9 15 6 16 15 19 16 11 10 6 14 11 11 8 9 5 [1] DISPLAY CITY-DISTANCE INFORMATION MATRIX [2] SHORTEST DISTANCE BETWEEN TWO CITIES [3] ADJACENT CITY DISTANCE FROM A CITY [0] Quit Enter Choice --> 2 0 ANG MO KIO 1 BEDOK 2 BUKIT BATOK 3 BUKIT PANJANG 4 BUKIT TIMAH 5 CHANGI 6 CHOA CHU KANG CLEMENTI 18 SERANGOON 19 TAMPINES 20 TOA PAYOH 21 TUAS 22 UPPER THOMSON 23 WOODLANDS Select a integer starting point: 0 Select a integer end point: 9 Start from: ANG MO KIO To: MANDAI Path: ANG MO KIO -> NEE SOON -> MANDAI Total Distance: 9km
