2. (12 pts) The Floyd-Warshall algorithm for solving the all pairs shortest path problem in a graph (with vertices that are numbered 1, 2, ..., V) iterates over k-1 to V, where at step k it has all shortest paths passing on the way through only vertices 1 through k. Indicate which of the following properties this algorithm has. a) (4 points) It is a greedy algorithm. If not, say what algorithm type it is. b) (2 points) At step k it already has the correct paths for best paths of length k+1 or shorter. c (3 points) The change in each shortest length from step k to step k+1 chooses the min of two terms, each requiring at most a single arithmetic addition to the shortest lengths at the end of step k. d) (3 pts) For sparse graphs with non-negative path lengths it is preferred to the repeated application of the Dijkstra algorithm over all vertices. Explain