2.3 Dijkstra on Dijkstra

You must submit this in an archive named "dijkstra.zip".

Flavor text: Dijkstra suddenly finds himself in a random graph. He must escape using only his TI-83 and his experience designing algorithms.

You must implement Dijkstra’s Shortest Path algorithm.

Your program should accept a description of an undirected graph in the following format:

where the first integer is the largest node and the RHS of an edge is greater than the LHS. (White space is allowed between any terms.)

You may want to write a program to generate such inputs.

Your program should accept two nodes and compute the shortest path between these nodes.

Your program should output the shortest path along with its cost in the following format:

Cost: <weight>

You must test your program on graphs of at least 1000 nodes.

Your program must output the time it took to solve the problem (not read in the input and solve the problem.)

If you want to, follow these directions instead.

2.1	Three Ways, One Quicksort
2.2	Planning the Attack with Graph Theory!
2.3	Dijkstra on Dijkstra
2.4	Longest Common Subsequence
2.5	Traveling He-Man