In dijkstra.cpp, create and document type Vertex. An object of type Vertex represents information about a vertex in a graph. In the program, each Vertex object will represent one vertex number. For example, there will be a Vertex object for vertex 1, another for vertex 2, etc.

A Vertex object that represents information about vertex number v has the following pieces of information.

A pointer to a linked list of all edges edges that are incident on v. This list is called an adjacency list, since it shows the vertices that are adjacent to v. The list cells have type Edge.

A real number indicating v's shortest distance from the start vertex. This number is 1 if the distance is not yet known. (This is the number called time(v) above. Descriptions of algorithms use convenient notation, not the notation that you find in a C++ program.)

A vertex number sender. (This is the number called sender(v) above.) After a signal has reached vertex v, the shortest path from v back to the start vertex begins by going from v to sender(v). So the senders allow you to reconstruct the entire shortest path.

Create a constructor for type Vertex that takes no parameters, sets the 'time' and 'sender' fields to 1, and sets the adjacency list pointer to NULL.

3. Type Edge

In dijkstra.cpp, create and document type Edge. An object of type Edge is a cell in an adjacency list. It represents an edge of the graph.

In the documentation for type Edge, make sure that you say that an object of type Edge is used as a cell in an adjacency list. The Edge structure stores:

Two vertex numbers u and v. Even though the graph is undirected, it is important to think of this edge as directed from u to v. It will be used in that direction in a path from the start vertex to the end vertex. Think of an edge as a divided road, consisting of two separate one-way roads. Document that important fact. Pay attention to this! Ignore it at your peril.

A weight w of the edge.

A pointer next that points to the next Edge in the linked list.

Create a constructor that takes four parameters (two vertex numbers, a weight and a next pointer) and installs them into the four fields of an Edge.

Important note. Because an edge is broken into two one-way parts, an edge between u and v must occur in two adjacency lists. The adjacency list for vertex u contains an edge directed from u to v. The adjacency list for vertex v contains an edge directed from v to u.

4. Type Graph

In dijkstra.cpp, create and document type Graph. An object of type Graph represents a weighted graph and stores the following.

The number of vertices.

The number of edges.

An array, vertices, where vertices[v] is a Vertex structure giving information about vertex v.

Create a contructor for type Graph that takes a number of vertices as a parameter. It should allocate an array for the vertices and set the number of edges to 0. Notice that it is not necessary to have a maximum number of vertices. You allocate the array after you know how many vertices there are.

The vertices are numbered starting at 1. The sensible thing is not to use index 0 in the array. Pay attention to that. You will need to allocate an extra slot in the array to account for the unused slot.

5. Draw an accurate picture of the representation of a small sample graph.

Skipping this step is a big mistake.

In the description of Dijkstra's algorithm, I have used time(v) for the time stored with vertex number v. But that is not how it is referred to in the C++ program. If you have Graph g, how can you get the time stored for vertex number 1 in g? How can you get the time stored for vertex number v? Look at your diagram.