Directed Graph

Let *G = (V, E)* be a directed graph, where *V* is the set of vertices and *E* is the set of edges. All the edges have attached integer weights (*Attention:* the weights may be also negative!). Assuming the graph is sparse, write a program finding the shortest paths from a given source vertex *S* to all the other vertices. Implement your algorithm such that if there is more than one shortest path from *S* to some vertex *v,* a path with the fewest number of edges will be chosen. * Note*: You may need to implement more than one shortest-path algorithm to ensure the efficiency, and decide which algorithm is better suited for your problem only after reading the input data about the graph. **Reading** **the data ** The graph information is read from a file *[login to view URL]*, where each line contains the name of a vertex (which is a string or an array of char’s1) followed by the names of their adjacent vertices and the weights of the arcs incident to them. For instance, the content of the file for the graph in Figure 1 is: A : B 8 D 4 F 5 B : D 1 E 3 G 6 C : A 4 F 2 D : C 9 E -7 F -1 G 4 E : G 5 F : G : F 10 1You may assume that the characters are only letters and digits. **Output ** For each vertex in the graph except *S*, print a shortest path with fewest edges from *S* to the vertex (print the names of the vertices on the path) together with its length. *Attention:* in case of negative cycles, the shortest path may not be defined. ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Deliverables must be in ready-to-run condition, as follows (depending on the nature of the deliverables): a) For web sites or other server-side deliverables intended to only ever exist in one place in the Buyer's environment--Deliverables must be installed by the Seller in ready-to-run condition in the Buyer's environment. b) For all others including desktop software or software the buyer intends to distribute: A software installation package that will install the software in ready-to-run condition on the platform(s) specified in this bid request. 3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement). ## Platform Windows XP Unix