In this problem you will implement Dijkstra's algorithm to find shortest paths between pairs of cities...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
In this problem you will implement Dijkstra's algorithm to find shortest paths between pairs of cities on a map. We are providing a GUI that lets you visualize the map and the path your algorithm finds between two cities. Before you start: Examine the Codio directory. You will find the file cityxy.txt which contains a list of cities and their (X,Y) coordinates on the map. These are the vertices in the graph. The file citypairs.txt lists direct, connections between pairs of cities. These links are bidirectional, if you can go from NewYork to Boston, you can go from Boston to NewYork. These are the edges of the graph. Compile all Java sources and run the program Display. At this point, click on the "Box URL" button along the Codio tool bar at the top of your screen. If you don't see "Box URL" along the toolbar. instead click on the little arrow next to "Project Index (static)" and from there you can select the "Box URL" option. From that point on you'll have the "Box URL" button on your tool bar. This should bring up a view of the computer's actual desktop screen. Inside, a window will have appeared with your running program that displays the map. You will notice that clicking on "Compute All Euclidean Distances does nothing and that "Draw Dijkstra's Path" will throw a null pointer exception on the terminal tab. You will have to implement these methods yourself. You can switch between this Virtual Desktop tab and any of your other tabs freely. Make sure you quit the Java program before running it again. You can do this by either clicking the small x at the top of the java application in the virtual desktop window or by ctri^cing the program from terminal. Carefully read through the classes Vertex.java and Edge.java, which represent the vertices and edges of a graph. You will not have to modify these classes for the assignment, but you need to understand how the graph is represented and what information is associated with each vertex and edge. You will only have to modify Dijkstra.java, which represents a graph and will contain your implementation of Dijkstra's algorithm. You will need to use the instance variable vertexNames, which contains a mapping from city names to Vertex objects after the graph is read from the data files. The main method of Dijkstra illustrates how the class is used by the GUI and might be useful for testing your implementation on the command line. • Implement the method computeAllEuclideanDistances () which should compute the euclidean distance between all cities that have a direct link and set the weights for the corresponding edges in the graph. Once this works correctly, the correct distances should be displayed in the GUI when clicking on "Compute All Euclidean Distances". 11 • In the method dobijkstra (String s), implement Dijkstra's algorithm starting at the city with name s. Use the distances associated with the edges. The method should update the distance and prev instance variables of the Vertex objects. You should not use a priority queue to store vertices that still need to be visited. Instead, keep these vertices on a List and scan through the entire list to find the minimum. We are making this simplification (at the expense of runtime) because java.util. PriorityQueue does not support the decreasekey operation. • Implement the method getDijkstraPath(String s, String t), which uses the distance and prev instance variables of the Vertex objects to find the shortest path betweens and t. This method should be called only after dodijkstra (String s) has been called with the start city. The resulting path should be returned as a list of Edge objects. Once this works correctly. you should be able to compute and display paths in the GUI. Note: Your program must work for repeated runs of dijkstra's algorithms on different city pairs. To make sure that your program does this, be sure that you reinitialize the bookkeeping fields (known, prev, and distance ) in the vertices stored in vertexNames at the beginning of each run of doDijkstra. In this problem you will implement Dijkstra's algorithm to find shortest paths between pairs of cities on a map. We are providing a GUI that lets you visualize the map and the path your algorithm finds between two cities. Before you start: Examine the Codio directory. You will find the file cityxy.txt which contains a list of cities and their (X,Y) coordinates on the map. These are the vertices in the graph. The file citypairs.txt lists direct, connections between pairs of cities. These links are bidirectional, if you can go from NewYork to Boston, you can go from Boston to NewYork. These are the edges of the graph. Compile all Java sources and run the program Display. At this point, click on the "Box URL" button along the Codio tool bar at the top of your screen. If you don't see "Box URL" along the toolbar. instead click on the little arrow next to "Project Index (static)" and from there you can select the "Box URL" option. From that point on you'll have the "Box URL" button on your tool bar. This should bring up a view of the computer's actual desktop screen. Inside, a window will have appeared with your running program that displays the map. You will notice that clicking on "Compute All Euclidean Distances does nothing and that "Draw Dijkstra's Path" will throw a null pointer exception on the terminal tab. You will have to implement these methods yourself. You can switch between this Virtual Desktop tab and any of your other tabs freely. Make sure you quit the Java program before running it again. You can do this by either clicking the small x at the top of the java application in the virtual desktop window or by ctri^cing the program from terminal. Carefully read through the classes Vertex.java and Edge.java, which represent the vertices and edges of a graph. You will not have to modify these classes for the assignment, but you need to understand how the graph is represented and what information is associated with each vertex and edge. You will only have to modify Dijkstra.java, which represents a graph and will contain your implementation of Dijkstra's algorithm. You will need to use the instance variable vertexNames, which contains a mapping from city names to Vertex objects after the graph is read from the data files. The main method of Dijkstra illustrates how the class is used by the GUI and might be useful for testing your implementation on the command line. • Implement the method computeAllEuclideanDistances () which should compute the euclidean distance between all cities that have a direct link and set the weights for the corresponding edges in the graph. Once this works correctly, the correct distances should be displayed in the GUI when clicking on "Compute All Euclidean Distances". 11 • In the method dobijkstra (String s), implement Dijkstra's algorithm starting at the city with name s. Use the distances associated with the edges. The method should update the distance and prev instance variables of the Vertex objects. You should not use a priority queue to store vertices that still need to be visited. Instead, keep these vertices on a List and scan through the entire list to find the minimum. We are making this simplification (at the expense of runtime) because java.util. PriorityQueue does not support the decreasekey operation. • Implement the method getDijkstraPath(String s, String t), which uses the distance and prev instance variables of the Vertex objects to find the shortest path betweens and t. This method should be called only after dodijkstra (String s) has been called with the start city. The resulting path should be returned as a list of Edge objects. Once this works correctly. you should be able to compute and display paths in the GUI. Note: Your program must work for repeated runs of dijkstra's algorithms on different city pairs. To make sure that your program does this, be sure that you reinitialize the bookkeeping fields (known, prev, and distance ) in the vertices stored in vertexNames at the beginning of each run of doDijkstra.
Expert Answer:
Answer rating: 100% (QA)
To implement Dijkstras algorithm to find shortest paths between pairs of cities on a map we can follow these steps 1 Compute all Euclidean distances b... View the full answer
Related Book For
Computer Networking A Top-Down Approach
ISBN: 978-0136079675
5th edition
Authors: James F. Kurose, Keith W. Ross
Posted Date:
Students also viewed these programming questions
-
How does the integration of positive psychology principles, such as strengths-based approaches and flow theory, contribute to the enhancement of motivation and well-being in individuals and...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
A devoted Indiana basketball fan needs $14,000.00 to attend the Final Four exactly one year from today. If the fan can earn 7.00% annually on his investments, how much should he set aside today?
-
An inclined manometer is a useful device for measuring small pressure differences. The formula given in Section 3.4 for the pressure difference in terms of the liquid-level difference h remains...
-
The ABC Evening News Report in a news segment on hypothermia research studies at the University of Minnesota claimed that heat loss from the body is 30 times faster in 10C water than in air at the...
-
MY Autobody s adjusted trial balance on December 3 1 , 2 0 2 3 , appears in the work sheet as follows: No . Account Debit Credit 1 0 1 Cash $ 2 7 , 6 0 0 1 2 4 Shop supplies 1 , 6 0 0 1 2 8 Prepaid...
-
Consider a European call option on a non-dividend-paying stock. The strike price is \(K\), the time to expiration is \(T\), and the price of one unit of a zero-coupon bond maturing at \(T\) is...
-
Big Bobs Burger Barn would like to graphically depict the interaction among its lunch-ordering customers and its three employees. Customers come into the restaurant and eat there, rather than drive...
-
Your client want to have $168,313 in 20 years, how much money should he put in a savings account today? Assume that the savings account pays you 5.5 percent and it is compounded annually.
-
Which series has the highest beta. BraveNewCoin Liquid Index for Bitcoin 1D BNC Trading Brave Ne Yellow Green Blue Orange
-
When a narrow beam of monoenergetic electrons impinges on the surface of a single metal crystal at an angle of 30 degrees with the plane of the surface, first-order reflection is observed. If the...
-
Prove that more informed heuristics develop the same or less of the search space. formalize the argument presented in Section 4.3.3. Data from section 4.3.3 The final issue of this subsection...
-
What issues of confidentiality and liability does the hospitals peer review function present?
-
A acquires 25 per cent of the voting shares of B on 1 January 2009. The purchase consideration was EUR 10m, and A has significant influence over B. The retained earnings of B were EUR 15m at the date...
-
Company X is executing a gigantic project of constructing the tallest building in the country. The project is expected to take three years to complete. The company has signed a fixed price contract...
-
LOral markets 34 brands of cosmetics, fragrances, and hair care products in 130 countries. The companys international strategy involves manufacturing these products in 42 plants located around the...
-
2. In calculating the unemployment rate, part-time workers are A. counted as unemployed because they are not working full-time. B. counted as employed because they are receiving payment for work. C....
-
The following selected accounts and normal balances existed at year-end. Notice that expenses exceed revenue in this period. Make the four journal entries required to close the books: Accounts...
-
As DHTs are overlay networks, they may not necessarily match the underlay physical network well in the sense that two neighboring peers might be physically very far away; for example, one peer could...
-
Because an integer in [0, 2/n - I] can be expressed as an n-bit binary number in a DHT, each key can be expressed as k =(k0' k1 . .. , k0_1,), and each peer idenn tifier can be expressed P =(p0' Pl'...
-
True or false: a. If stored video is streamed directly from a Web server to a media player, then the application is using TCP as the underlying transport protoco\' b. When using RTP, it is possible...
-
Continue with the case of Hindustan Lever Ltd. Analyse the news items to predict the future outlook of the company and to strategise its improvement. Attempt the following requirements towards this...
-
Form a small group. Concentrate on BSE Sensex companies and compile the voluntary disclosures made by each of them. Draft a crisp research paper highlighting your findings and use thereof to various...
-
Hassan Abu-Jihaad was convicted of disclosing national defense information and of providing material support to terrorist by a jury in the District Court of Connecticut. Abu-Jihaad moved for a...
Study smarter with the SolutionInn App