You have chosen to sponsor your bid up to a maximum amount of .
(1) Read Wikipedia article “Shortest path problem” at
(2) Read in a directed weighted diagram from the keyboard and store the diagram into a
array-based graph implementation.
(3) Input two vertices (e.g. index numbers) from the keyboard as the starting and ending
nodes of a path.
(4) Use A*
algorithm to calculate the shortest (with the least weight) path between these two
(5) Display the path to both a text file and the standard output device such as a printer or
(6) Create a directed graph with non-negative weight on each edge that represents
commercial flights in continental USA. These values of weight can be interpreted as the
price of fights between adjacent two cities.
(7) There should be at least 30 cities and should be some combined path made of multiple
edges that has total weight less than shorter paths that connect the same pair of cities.