Homework 9, CPSC 4100-01 solution

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