In this part of the assignment you will implement a graph representation to be used later in Part II.

The assignment has these files provided:

**Graph.java**- Graph interface.**Vertex.java**- Vertex class.**Edge.java**- Edge class.**MyGraph.java**- Implementation of Graph interface, you will need to fill in code here.

You are to add code to **MyGraph.java** that implements the **Graph.java** interface. **Graph.java**
makes use of the **Vertex.java**
and** Edge.java** classes
provided. You are free to add things to **Vertex.java,** **Edge.java**, or** ****MyGraph.java**, just don’t remove anything
that is currently there. You should **not** modify **Graph.java**. Your code should be efficient and strive for
the minimal big-Oh possible for the requested operations. Although a simple list of vertices and edges
is sufficient to store all information about a graph, it may not be the most
efficient method for answering questions about the graph (like those described
in part II.)

**Grading (please note anything which fails these functions might lead points reduction): **

[2 pts] public Collection edges() [2 pts] public Collection vertices() [8 pts] public Collection adjacentVertices(Vertex v) [8 pts] public int isAdjacent(Vertex v, Vertex w)

In this part of the assignment, you will use the graph representation you
created in Part I to read a description of a graph and answer questions about
it. In particular, you should use Dijkstra's
algorithm to find shortest paths in the graph.
You will do this by filling in code for the shortestPath method in **MyGraph.java**. You may assume that graphs you are given will
not contain negative cost edges. A
description of the shortestPath method
from **MyGraph.java**
appears below:

Returns the shortest path from a to b in the graph. Assumes positive edge weights. Uses Dijkstra's algorithm.

@param a the starting vertex

@param b the destination vertex

@param path a list in which the path will be stored, in order, the first being the start vertex and the last being the destination vertex. The list will be empty if no such path exists. NOTE: the list will be cleared of any previous data. path is not expected to contain any data needed by the method when the method is called. It is used to allow us to return multiple values from the function.

@return the length of the shortest path from a to b, -1 if no such path exists.

@throws IllegalArgumentException if a or b does not exist.

**/

public int shortestPath(Vertex a, Vertex b, List<Vertex> path) {

**Grading (please note anything which fails this function might lead points reduction): **

[20 pts] public int shortestPath(Vertex a, Vertex b, List<Vertex> path)## Style (6 points)

**Driver Program:** We have provided a driver program to read in input
from the user:

**Paths.java**– driver program that reads in vertex and edge files, creates a graph and prompts use for vertices to find shortest path between.

When the program begins execution, it reads the two data files and creates a
representation of the graph. Although
not required, you may find it useful to provide some way to print or display
the graph at this point to ensure that it has been read and stored
properly. Once the graph has been built,
the program loops repeatedly and allows the user to ask for information about paths
in the graph. The user should enter two
vertex names. If there is a path from
the first to the second vertex, the program will describe the shortest
(cheapest) such path, including the vertex names on the path and the total
length (cost). For example, if the user
enters `SEA`

` DEF`

, then the output might look like `SEA ABC DEF 520`

if the shortest path
from `SEA`

to `DEF`

runs through vertex `ABC`

and has a total length of `520`

.

You should modify **Paths.java** so that
if there is no path between the two requested vertices, a descriptive message
should be printed.

**Input file format**: You will need
two input files, whose format is as follows:

**Vertices**: This file has one line per vertex and each line contains a text string with the vertex name.**Edges**: This file has three lines per directed edge. The first line gives the starting vertex. The second line gives the ending vertex (the one being pointed to). The third line is a string of digits that give the distance (or weight) on that edge (this line should be converted to a number to be stored in the graph).

You may assume that every vertex name that appears in an edge also appears in
the vertex list. Note that since data
files are expected to represent *directed*
graphs, the existence of an edge from a to b does not guarantee the existence
of an edge from b to a (unless both edges exist in the data file), nor does it
guarantee that the weight of the edge from a to b is the same as the weight of
the edge from b to a. You may assume
that negative weight edges will not be present in input files you are given
(although zero weight edges may exist).

Two
sample data files are available representing information about airports and the
cost of a flight between them. File **vertex.txt**
contains a list of 3-letter airport codes, each of which represents a vertex in
a directed graph. File **edge.txt**
contains information about the directed edges in the graph.

1) Fill in the method bodies as described in Part I and Part II.

2) Make the slight modification to the provided driver program as requested.

3) Answer the write-up questions below.

**Note**: You **may** use Java collection
classes for this assignment.

Include the following in a file called `readme.txt:`

1) A description of the worst case big-O running time of your implementations of these methods:

·
adjacentVertices

·
isAdjacent

·
shortestPath

Please use variables E and V in your answers and ** explain
how you got the values you did**.

2)
A short description of any **extra credit** extensions included in
your code or data files. Be sure to
include a brief summary of **how to
operate your program**, if you have added new features.

You should turn in the following electronically:

- ALL of the files that make up
your program. (Including at
least: Graph.java,
Vertex.java, Edge.java, MyGraph.java, Paths.java)You should NOT
change Graph.java however.
(Please turn these in as individual files, not zipped
together. Your TAs thank you!)
- Your
`readme.txt`

file containing your write-up as described above. - Any additional data or other
files you developed to work with your program. (These should be described briefly in
the
`readme.txt`

file.) - If you did any
, please put those files in a separate folder/zip file. Include all files needed to run any extra credit options in the zip file.__extra credit__

A small amount of extra credit will be awarded for interesting extensions. Here are a few possibilities:

- (3
points) Improve your implementation of Dijkstra’s by using a
**priority queue**. For this, you could modify code from the textbook or start from scratch. Note that for Dijkstra's algorithm, we need to be able to find items in the priority queue and update their priorities. The simplest implementation of this can just do a sequential scan to locate an item, then adjust the priority, and move the item to its proper place in the heap. A more complex implementation would allow items in the priority queue to be accessed in constant time on average. A simple sequential search of the priority queue is fine for small graphs, but for large graphs we would like to be able to find items in constant time so the total time needed to update a priority is a constant plus the log n time needed to reestablish the heap property in the priority queue. There are various ways to do this, including keeping a back-pointer from each vertex to its entry in the priority queue. - (3
points) Find the
**unweighted shortest path**. In other words, find the minimum number of edges that must be traversed from the start to the destination, ignoring the weight of each edge. - (3
points) Given a vertex in the graph, compute a
**minimum spanning tree**from that vertex and print a list of the edges in the MST in the order in which they are added to the tree. - (3
points) Other
**graph algorithms**, check with the instructor first. - (3
points)
**Graphical displays**: Display the graph as a drawing; allow the user to select endpoints by clicking on the screen; highlight the path visually; etc. - (1 point) More/better/interesting data files. The supplied data files are quite minimal. Data describing more extensive graphs, other kinds of graphs, or graphs with additional information such as coordinates or locations on a map would be great.

I’m open to others ideas as well, please talk to me if you have other ideas!