Description
1) How can we use the output of the Floyd-Warshall algorithm to detect the presence of a negative-weight
cycle? [CLRS 25.2-6]
15 points
2) Diameter of a graph is the longest distance (in terms of number of hops) between any two vertices. Propose
an efficient algorithm to determine the diameter of a given graph.
15 points
3) Professor Gaedel has written a program that he claims implements Dijkstraβs algorithm. The program
produces π£. π and π£. π for each vertex π£ β π. Give an π(|π| + |πΈ|)-time algorithm to check the output of the
professorβs program. It should determine whether the π and π attributes match those of some shortest-paths
tree. You may assume that all edge weights are nonnegative. [CLRS 24.3-4]
20 points