*Due Friday, February 7 at 5:00 PM. ^{1} Please refer to the homework policy here.*

Let be a directed graph with real-valued edge weights and no negative cycles. We define the "even distance" between two vertices as the length of the shortest walk from to using an even number of vertices.

^{2}- Design and analyze an algorithm
^{3}to compute the even distance between every pair of vertices when the edge weights are nonnegative. - Design and analyze an algorithm
^{3}to compute the even distance between every pair of vertices when the edge weights are real-valued, and there are no negative cycles.

- Design and analyze an algorithm
Design and analyze an algorithm

^{3}that, given a directed graph with real-valued edges, detects if there is a negative cycle.

2 Here we mean an even number of vertices counting multiplicity, and an odd number of edges counting multiplicity. So a walk like counts for "even distance" because there are 6 vertices counting multiplicity ( appears twice, and each appear once , which adds up to 6). ↩