Write a program that reads information about a weighted graph from the standard input. The input format starts with a description of a graph in the same format as for Assignment 5. After that are two vertex numbers: a start vertex s and an end vertex e.

Your program should print, on the standard output, a description of the graph followed by the shortest path from s to e and the distance from s to e via that path.

For example, the input might look like this.

5 1 2 9.0 1 3 12.0 2 4 18.0 2 3 6.0 2 5 20.0 3 5 15.0 0 1 5  

That says that there are five vertices. There is an edge from vertex 1 to vertex 2 with weight 9.0, an edge from vertex 1 to vertex 3 with weight 12.0, etc. The line containing only 0 indicates the end of the edges. The start vertex s is 1, and the end vertex e is 5. The output for this input would be as follows.

There are 5 vertices and 6 edges. The edges are as follows. (1,3) weight 12.000 (1,2) weight 9.000 (2,5) weight 20.000 (2,3) weight 6.000 (2,4) weight 18.000 (3,5) weight 15.000 The shortest path from 1 to 5 has length 27.000 and is 1 -> 3 -> 5  

The order of the edges is not important, but each edge should be shown once.

An Algorithm for Finding Shortest Paths

Discrete Event Simulation

A discrete event simulation performs a simulation of a collection of events, where each event occurs at a specified time. The simulation jumps from one event to the next. If one event occurs at 1:00 and the next occurs at 2:00, the simulation does not sit and wait for an hour. It just updates its internal clock to 2:00 and moves on.

As each event is encountered, it is processed. A key characteristic of discrete event simulations is that processing one event can cause more events to be created.

An example is a simulation of a bank with tellers and customers. There are five kinds of events.

A teller is ready to serve a customer. This event is processed by placing the teller into the teller queue. If the customer queue is not empty, it also schedules a "teller begins to serve customer" event at the current time.

A customer arrives. Processing a customer arrival adds the customer to the customer queue and also schedules another customer arrival at some randomly chosen future time. That way, customers keep arriving. The distribution of random times determines how rapidly customers arrive.

If there is a teller in the teller queue, then a "teller begins to serve customer" event is scheduled at the current time.

A teller begins to serve the next customer. Processing this event removes the first customer from the customer queue and removes the first teller from the teller queue. It also schedules a "teller finishes serving customer" event at some randomly chosen future time. The distribution of this random number controls how much time it takes to process a transaction.

A teller finishes serving a customer. Processing this event schedules a "teller is ready to serve customer" event at the current time.

Stop the simulation. Processing this event stops the simulation.

Additionally, when each event is processed, it writes out the current simulation time and the event that is being performed. It also keeps track of some statistics, such as how long a customer waited for service on the average.

It is easy to get the simulation started. If there are t tellers, then schedule t "teller is ready" events at time 0, the beginning of the simulation. Also schedule a "stop" event at some future time so that the simulation will not continue forever.

The simulation is performed by an event loop, that is roughly as follows.

 loop Get the chronologically next event. Call it E. Process event E. until the simulation has stopped  

Discrete event simulations are useful for games. Each event is something that happens in the game, such as a character taking a step forward. Processing an event can cause new events to be sheduled, such as taking another step forward. It is easy to schedule the arrival of new characters at specific times.

Dijkstra's Algorithm

Dijkstra's algorithm finds shortest paths in weighted graphs, and it can be expressed as a discrete event simulation.

Instead of thinking of each edge as having a distance, think of the weight of an edge as a time, in seconds. The simulation imagines sending signals between adjacent vertices. A signal from vertex u to vertex v along an edge of weight w takes w seconds to reach v.

During the simulation, the algorithm keeps two pieces of information about each vertex v.

The arrival time (v.time) of the first signal to reach v. If no signal has reached v, then v.time is 1.

The vertex (v.from) that sent the signal to v that was the first signal to reach v. If no signal has reached v, then v.from is 1.

There is just one kind of event: A signal from vertex u arrives at vertex v at time t. Let's write that event in a more compact form as (u, v, t).

Processing event (u, v, t) goes as follows.

If v.time 0, then do nothing, since this is not the first signal to reach v. For the remaining cases, assume that v.time < 0.

Set v.time = t and v.from = u.

For each vertex r that is adjacent to v, where no signal has yet reached r, send a signal from v to r by scheduling an event (v, r, t + w) where w is the weight of the edge from v to r. That is, this signal arrives at r just w seconds after the signal reaches v.

To get started, create an event that represents a signal arriving at the start vertex from a fictitious vertex 0 at time 0. After that, go into the event loop. Keep going until a signal reaches the end vertex.

A Refinement Plan and Additional Requirements

Getting Started

Getting started

1. Create a directory for assignment 7 and create file dijkstra.cpp. Copy the template into it.

Add a comment to dijkstra.cpp telling its purpose. Include a description of the input format as well as an example input and output.

Representing Graphs: Types Vertex, Edge and Graph

This assignment uses a different graph representation from assignment 5. Here, we use the adjacency list representation.

Types and information representation

2. Type Vertex

Create and document type Vertex. Each vertex v has the following pieces of information.

A pointer to a linked list of edges listing all edges that are incident on v. This list is called an adjacency list.

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 v.time above.)

A vertex number from. (This is the number called v.from above.) After a signal has reached vertex v, the shortest path from v back to the start vertex begins by going from v to v.from.

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

3. Type Edge

Create and document type Edge. Type Edge is used for a cell in an adjacency list. The Edge structure stores:

Two vertex numbers u and v.

A weight w.

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.

Important note. An edge between u and v must occur in two adjacency lists, the list for vertex u and the list for vertex v, since it can be used to go from u to v or from v to u. Think of a bidirectional road being split into two one-way roads.

Important note. Since the roads are actually one-way, the order of the vertices matters. Choose an order. For example, an edge from a to b might be stored with u = a and v = b, not the other way around.

4. Type Graph

Create and document type Graph. A graph 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 v.time for the time stored with vertex number v. But that is not how it is referred to in the program. If you have Graph g, how can you get the time stored for vertex number 1 in g? For vertex number v?

Input and Echoing

Input and echoing

6. Reading the Graph

Document and define a function to read a graph. You can use your function from assignment 5 as a starting point, but be careful to notice that the graph representation has changed.

Do not change the graph representation to make the old graph reader work unchanged. Use the adjacency list representation. Do not use duplicate representations. Only store the graph once, using the adjacency list representation.

7. Printing a Graph

Document and define a function to print a graph. Again, you can use your function from assignment 5 as a starting point, but make sure to convert it to the new graph representation.

Below, you will use a global variable to control tracing. If tracing is turned on then show each edge twice, once for each adjacency list that it occurs in. If tracing is turned off, then show each edge once. That is easy to arrange. When looking at an edge from u to v, only show it if u < v.

8. Testing

Test reading and echoing the graph, both with tracing turned on and turned off. Do not move on until you are satisfied that this much works

I need help writing steps 6 and 7. Here is what I have so far:

#include

#include

#include

using namespace std;

struct Edge{

int vertexNumber;

double weight;

struct Edge* next;

Edge( int vn, int wgt, struct Edge* nxt ){

vertexNumber = vn;

weight = wgt;

next = nxt;

};

};

struct Vertex{

struct Edge* adjacencyList;

double shortestDistance;

int vertexNumber;

Vertex(){

vertexNumber = shortestDistance = -1;

adjacencyList = NULL;

}

while(head->next != NULL) {

head = head->next;

return;

}

head->next = node;

}

};

struct Graph{

int nVertices;

int nEdges;

struct Vertex* vertices;

Graph( int nVert ){

vertices = new struct Vertex[nVert];

nEdges = 0;

nVertices = nVert;

}

};

int main(int argc, char** argv)

{

Graph * g = readGraph();

int n,c;//modified

cin>>n>>c; //modified

printGraph(g);

return 0;

}