a. Consider the weight matrix D output by the Floyd-Warshall algorithm. Assume the weight of an edge e(a,b) is decreased from we to we. Design an efficient algorithm to update matrix D with respect to this change, and provide its runtime.

b. Modify Johnsons algorithm to output the shortest path distances also in the presence of negative-weight cycles. That is, if there is a negative-weight cycle that contains vertex v, then Dv,u = for any vertex u