Q)a)(T/F) Let G = (V, E) be a directed graph with arbitrary (possibly negative) edge weights. Suppose, s,t ? V are two distinct vertices in G such that all directed paths from s to t in G contain no cycles, and at least one such path exists. Then, the Bellman-Ford algorithm, starting from a source vertex s, will correctly calculate the weight of a shortest path from s to t, even if G contains negative cycles.

b) (T/F) In a weighted graph G, if k is the maximum number of edges in shortest paths between any two vertices, then it is possible to reduce the running time of Floyd-Warshall to O(kn²) by finishing early.