Q)a)(T/F) Let G = (V, E) be a directed graph with arbitrary (possibly negative)
ID: 3712537 • Letter: Q
Question
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(kn2) by finishing early.
Explanation / Answer
a) True
shortest path is found for a vertex for which shortest path is well defined even if it contains negative weight cycles
b) <False>
Floyd Warshall iterates over list of all vertices in the order , until the last loop it will not find the shortest path
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.