AE2ACE Coursework 2020-2021 on the Shortest-Path Problem This is the second assessed coursework. It is worth 12 % of the final mark. Deadline: 3 May 2021 16:00 Problem Description For this coursework, you need to design and implement a Java program that solves the “all-pairs shortest paths problem”, i.e. the shortest path from each vertex v to every other vertex u. For example, the shortest distances of Node 0 to all other nodes are: d0,1, d0,2, ..., d0,n, then the summation for Node 0 is: d0=d0,1+d0,2+...+d0,n. You should find the summation of the distance for all nodes d=d0+d1+d2+...+dn. Dijkstra algorithm is often used to find the shortest path of a graph. There are advanced algorithms which could find the shortest path faster, e.g. Johnson Algorithm (https://www.javatpoint.com/johnsons-algorithm). Floyd-Warshall Algorithm (https://www.javatpoint.com/floyd-warshall-algorithm) We may often encounter many shortest path problems in life, e.g., to find the optimal driving path from one place to another across the city; to route a packet through the internet from your PC to the server. In this coursework, we will practice how to find the optimal path from one city to another given a graph. The final output should be the sum of all-pair shortest distances. Task Description You must program it in Java. You must follow good programming practice. Your program must return the distance d within the given execution time. Temporally it is set to 1 second (The complete execution time). Note that your program may need to run efficiently in order to finish the execution in time for challenging test cases. 6 test cases will be used to evaluate your program. Each test case carries 2 marks. 2 sample test cases are provided. The final test scripts will be similar but different from these two test cases. Note that there will be 2 challenging test cases to check the efficiency of your program. An automated tester will be used to evaluate your program. Make sure that your program could execute successfully on sample test cases. Guidelines You may find the sum of distances by applying Dijkstra’s algorithm on each node. It is likely this implementation may pass the simple test cases, but not the time-critical challenging ones. You may need to conduct a preliminary research on this problem and find the most efficient implementation, e.g. Floyd-Warshall algorithm. You may implement Dijkstra’s algorithm using heap or Fibonacci heap for efficiency. Name your main java file as CW2.java. Define the main function inside this class, and all other functions you need inside this file. Input format: test case is stored in an input text file. Your program should take the text file name as the input and get the data from the input text file. All the test graphs are non-negative weighted graph. The graph is stored as edge list, e.g. u 84 82 433 u 18 87 270 u 10 18 341 u 19 14 686 d 51 58 459 For each line, the first character denotes whether it is a directed edge or an undirected edge, e.g. ‘u’ denotes an undirected edge and ‘d’ denotes a directed edge. The next two numbers denote the vertex indices, and the last number is the weight between them. You can assume the numbers are all non-negative integers. If a node is not reachable from another, set the shortest distance between them as 0. You should use one of the following ways to read the input file. private static final Scanner input = new Scanner(System.in); OR BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Output format: Your code should return the sum of distance d by printing it to on the screen. You must NOT print any intermediate results to the screen. We will use a ICPC local judge Lemonlime to test your program. A quick reference to install Lemonlime and how to use it to test your program is provided on Moodle. You may install it on your local machine and use it to evaluate your program, especially the input/output format and the execution time. You do NOT need to handle possible overflow. Marking (In total 12 marks) 6 test cases will be used to evaluate your program. Each test case carries 2 marks. If the sum of all distances for a test case is correct, you get 2 marks, otherwise you will get 0 mark. In total there are 12 marks for the coursework. If your program is not executable, you will get 0 mark for the coursework. If your code is not programmed in Java, you will get 0 mark for the coursework. If you have no comments in your code, you will get 0 mark for the coursework. Reference and Plagiarism If you use code you found in a textbook or on the web, you MUST acknowledge it. We will run the plagiarism detector tools to check for similarities between submissions and web-based material. You are reminded of the School's Policy on Plagiarism. How to submit Online submission via Moodle. You MUST put all your codes inside ONE file named “CW2.java” and zip the file. You MUST NOT use any sub-folders or submit any other files. You DO NOT need to submit any report. You should name the zip file using your name and student ID, e.g. “DongChen_1234567.zip”. Please note that every next submission overwrites all the files in the previous one. Do download your submission and check the integrity of your submission. You are reminded that if your submission is corrupted or not executable, you will receive 0 mark for this coursework.
欢迎咨询51作业君
