USING C++

Given a small graph whose vertices are labeled with some subset of the set of capital letters A, B, C, , Z. Suppose input file edges.dat contains the edges of the graph listed in random order, one per record. This problem asks you to write a program to find the shortest path through the graph from vertex A to vertex Z, if such a path exists.

As an example, consider the graph: A C W S Z

D Q T

For this example, the file edges.dat would consist of the edges

AD DQ CQ QC QT TW WC WS SZ TZ

in some order. Note that graphs are directed, in that edges are unidirectional, running from the first vertex to the second vertex but not conversely unless specifically listed both ways, e.g., CQ and QC above. We also agree that graphs do not have self-edges, i.e., no edge starts and ends at the same vertex. To repeat: write a program which inputs the file edges.dat and finds and outputs (to the file edges.out) the shortest path from vertex A to vertex Z, or which reports that no such path exists. (In the event of a tie, you can report any one of the shortest paths.) You should also report out the length of the shortest path. So for our example, your output should be:

AD DQ QT TZ total path length = 4.

Moreover, if we modify our example by removing edge TZ, the output should change accordingly to:

AD DQ QT TW WS SZ total path length = 6.

Finally, if we reverse the arrow on edge QT (that is, remove edge QT and add edge TQ), our output should now be:

no path from A to Z exists.