1. Suppose all the edge weights in a graph are integers between 1 and |E|. How fast can Dijkstra's algorithm be implemented?
2. Write a program to solve the single-source shortest-path problem.
3. a. Explain how to modify Dijkstra's algorithm to produce a count of the number of different minimum paths from v to w.
b. Explain how to modify Dijkstra's algorithm so that if there is more than one minimum path from v to w, a path with the fewest number of edges is chosen.
4. Find the maximum ?ow in the network.
5. Suppose that G = (V, E) is a tree, s is the root, and we add a vertex t and edges of in?nite capacity from all leaves in G to t. Give a linear-time algorithm to ?nd a maximum ?ow from s to t.