Graph C++ Dijkstra Shortest Path

The task

Your task is to use Dijkstras algorithm to find the shortest path between two points in a graph, by the following steps:

1. Define a generic Graph class, parameterized by the type of node labels in the graph. For efficiency, you should use numbers from 0 to n 1 to represent nodes (where n is the number of nodes) inside your class. This means you will need to maintain a two-way correspondence between labels and numbers; when presented with a label, you either map it to an existing number or extend the correspondence giving it a new number. One way to do this is with a map in one direction and a vector in the other.

You will also need to store the edges, in such a way that you can determine whether there is an edge from one node to another, and if so what its cost is. (Use double for costs.) For the above algorithm, you also need to be able to go through the edges out of a given node. A 2-dimensional vector would work, but it would be wasteful in the common case where only a fraction of the possible edges are included. So I suggest a vector of maps for this purpose.

Your class should include (at least) public member functions to

• return the number of nodes in the graph.
• test whether a label already occurs in a graph.
• map labels to node numbers and vice versa.
• given two labels and a cost, add an edge to the graph. (In there is already such an edge, replace its cost.)

You should also provide a means to determine the cost of the edge between two nodes, given their node numbers.

2. Add a global function read graph to read graph data from a file graph.txt. Each line of this file should consist of 3 words describing an edge: the start and end nodes and a number for the cost. You may assume that this file has the correct format.

3. Add to the Graph class a member function that takes two node numbers and uses Dijkstras algorithm to find a minimal path from the first to the second. It should either report that no such path exists or return one in a container. This function (and all the others in the Graph class) should not do any I/O. Try to keep all the temporary state associated with path finding local to this function and others it may use.

4. Add a main function that reads two node labels and either reports that no path from the first to the second exists, or prints the node labels of the shortest path, one per line, each preceded by its distance from the start. (So the first line with contain 0 and the start label, while the last will contain the total distance and the destination node label.)