# 数据结构代写 | CSCI203 ASSIGNMENT THREE

This assignment involves extension to the single source-single destination shortest path problem.

### Program:

1. Read the name of a text file from the console. (Not the command line)
2. Read an undirected weighted graph from the file.
3. Find the shortest path between the start and goal vertices specified in the file.
4. Print out the vertices on the shortest path, in order from start to goal.
5. Print out the length of the shortest path.
6. Find the second shortest path between the start and goal vertices.
7. Print out the vertices on the second shortest path, in order from start to goal.
8. Print out the length of the second shortest path.

The data files are constructed as follows:

• Two integers: nVertices and nEdges, the number of vertices and edges in the graph.
• nVertices triples consisting of the vertex label and the x‐ and y‐coordinates of each vertex. (An
int followed by two doubles)
• nEdges triples consisting of the labels of the start and end vertices of each edge, along with its
weight. Note: the weight associated with an edge will be greater than or equal to the Euclidean
distance between its start and end vertices as determined by their coordinates. (Two ints
followed by a double)
• Two vertex labels, the indicating the start and goal vertices for which the paths are required.
(Two ints)

A possible solution to the second shortest path problem is as follows:

For each edge ei on the shortest path:
Find the shortest path on (V, E – {ei}).
The shortest of these is the second shortest path.

Output to standard output will consist of the following data:

• The number of vertices and number of edges in the graph
• The start and goal vertices
• The Euclidean distance between the start and goal vertices calculated using their coordinates
• The vertices on the shortest path, in order from start to goal.
• The length of the shortest path.
• The vertices on the second shortest path, in order from start to goal.
• The length of the second shortest path.

## Implementation Requirement:

1) Part of the purpose of this subject is to gain an in-depth understanding of data structures and algorithms.
As such, all programming tasks in this subject require you to choose appropriate data structures and
algorithms, and to implement them yourself.

2) You may use any data structures or algorithms that have been presented in class. If you use other data
structures or algorithms appropriate references must be provided.

3) Programs must compile and run under gcc (C programs), g++ (C++ programs), java or python3.
Programs which do not compile and run may receive no marks.

4) Programs should be appropriately explained with comments.

5) All coding must be your own work.

6) Use of STL, Java Collection, collection framework and any third party libraries of data structures and
algorithms in your language choice is disallowed.

7) If you use any references other than the lecture notes, ensue you cite them or you may receive 0 marks
for plagiarism. A clear comment in your code is sufficient.

8) Code sourced from textbooks, the internet, etc may also not be used unless it is correctly credited. In
the event that you use code sourced in this way you will not receive marks for that part of the program.

9) You may use dynamic memory allocation to create the data structures you need at the start of program
execution.