COSC 2P03 Advanced Data Structures: Assignment 4

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

 Work according to the instructions given in the assignment.. algorithms

 

 

Your Tasks (8 Marks) 1. Define a class named TransportNet which has data attributes to represent the graph (i.e. the transportation network) and has methods as required below.

2. Within the TransportNet class, define a method named readData to read the information from the two attached CSV text files (cities.txt for vertices in your graph, distances for edges in your graph). These two files will help you create your weighted undirected graph. You should use adjacency matrix to represent edges. (1 mark)

3. Within the TransportNet class, define a method named findShortestPath based on Dijkstra’s algorithm to find the shortest path between two given cities on the graph. For example, if you call findShortestPath( "Windsor", "Ottawa"), it should return the shortest path (i.e. a sequence of city names) and the total cost (i.e. the sum of weights on the shortest path). You can either use Java’s built-in priority queue implementation or implement it yourself. (2 marks)

4. Within the TransportNet class, define a method named MST based on Kruskal’s idea to return a minimum spanning tree of your graph and the total cost of this tree (i.e. the sum of weights on the tree). You are allowed to use code from the textbook and lecture slides. (3 marks)

5. In the main function, create an instance/object (with name tn) of your TransportNet class. Call readData() to create your graph. Call functions findShortestPath( "Windsor", "Ottawa") and findShortestPath( "Arnprior", "NOTL"). After each call of this function, you should write your results into a text file named results.txt. Use file IO rather than copy-and-paste printed messages from the screen. Furthermore, call MST() and then write the returned results to the results.txt file. (1 mark) Program comments: to maximize readability, you should properly comment your program. (1 mark)

Attachments:

Expert's Answer

1128 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of