CSE310代做、programming代做、代写C++语言、C++程序语言调试

日期：2020-04-28 10:36

CSE310 Project 2: Finding a Shortest Path

Posted: Thursday, 04/02/2020, Due: Sunday, 04/26/2020

This is a programming project. You should use the C++ programming language, not any other

programming language. All programs will be compiled and tested on gradescope. You will

need to submit it electronically at gradescope, in one zip file, named CSE310-P02-Lname-Fname,

where Lname is your last name and Fname is your first name. The zip file should contain a set of files

that are absolutely necessary to compile and execute your program. Refer to the announcement

on April 12 for submission instructions.

In your first programming project, you have implemented the max-heap data structure and

its associated functions. In this programming project, you have to implement the min-heap data

structure and its associated functions. You have also to expand the fields of ELEMENT to contain

other fields as needed. Then you will add a module to implement Dijkstra’s shortest path algorithm.

Your program should be able to read in a graph, and build the edge adjacency list of the graph.

Note that the edge adjacency list is an array (indexed by the vertices) of singularly linked lists,

where the list according to a node v denotes the outgoing neighbors of node v. When given a

source-destination pair, your program should compute the shortest path from the source to the

destination, and output the result as required. Dijkstra’s shortest path algorithm uses a min-heap

of the vertices of the graph, where the key value at a node is the currently known distance from the

source to the given node. You have to define the data types as needed.

You should implement a module that takes the following commands from the key-board and

feed to the main program:

• S

• R

• W

• F s t iFlag

On reading S, the program stops.

On reading R, the program reads in an edge weighted directed graph from file Ginput.txt, builds

the adjacency lists, and waits for the next command.

The file Ginput.txt is a text file. The first line of the file contains two integers n and m, which

indicate the number of vertices and the number of edges of the graph, respectively. It is followed

by m lines, where each line contains three integers: u, v, and w. These three integers indicate the

information of an edge: there is an edge pointing from u to v, with weight w. Please note that the

1

vertices of the graph are indexed from 1 to n (not from 0 to n − 1).

On reading W, the program writes the graph information to the screen, and waits for the next

command.

The screen output format of W is as follows: The first line should contain two integers, n and

m, where n is the number of vertices and m is the number of edges. It should be followed by n

lines, where each of these n lines has the following format:

u : (v1, w1); (v2, w2); . . . ; (vk, wk)

On reading F s t 1, the program runs Dijkstra’s shortest path algorithm to compute a shortest

s-t path, and prints out the length of this shortest path to the screen, and waits for the next

command. The information printed to the screen should be of the format: LENGTH: l, where l is

the path length.

On reading F s t 0, the program runs Dijkstra’s shortest path algorithm to compute a shortest

s-t path, and prints out the path of this shortest path to the screen, and waits for the next command.

The information printed to the screen should be of the format: PATH: s, v1, v2, . . . , t, where the

vertices listed gives out the path computed.

Please note that your program should read in only one graph, but may be asked to compute s-t

shortest paths for different pairs of s and t. Therefore, during the computation of the s-t shortest

path, your program should not modify the given graph.

You should use modular design. At the minimum, you should have

• the main program as main.cpp and the corresponding main.h;

• the heap functions heap.cpp and the corresponding heap.h;

• the graph functions graph.cpp and the corresponding graph.h;

• various utility functions util.cpp and the corresponding util.h.

You should also provide a Makefile which compile the files into an executable file named proj2.

Grading policies: We will manually check your submission to see whether you have provided a

functioning Makefile (10 points), implemented modular design (10 points), provided documentation

(10 points), and performed graph I/O (10 points) (40 points total). The remaining 60 points come

from the posted + unposted test cases. There are 30 posted test cases (which can you view yourself

on Canvas) and 30 unposted test cases (which are not visible to you). When you submit your

project to gradescope, you will see immediately how many of these test cases you pass, and thus

how many points you get for this grading criteria.

2

(10 pts) You should provide a Makefile that can be used to compile your project on gradescope. The

executable file should be named proj2. If your program does not pass this step, you will receive

0 on this project.

(10 pts) Modular design: You should have a pair of implementation and header files for each of the

following: utility, heap, graph.

(10 pts) Documentation: You should provide sufficient comment about the variables and algorithms.

You also need to provide a README file describing what you are trying to achieve in this

project.

(10 pts) Graph I/O: The program reads the graph from a file into memory and outputs the necessary

information.

(30 pts) Your program should produce the correct output for a posted set of test cases.

(30 pts) Your program should produce the correct output for an unposted set of test cases.

3