Homework 6

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

  1. 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

    1. Design and analyze an algorithm3 to compute the even distance between every pair of vertices when the edge weights are nonnegative.
    2. Design and analyze an algorithm3 to compute the even distance between every pair of vertices when the edge weights are real-valued, and there are no negative cycles.
  2. Design and analyze an algorithm3 that, given a directed graph with real-valued edges, detects if there is a negative cycle.

 


1 We pushed back the deadline to Friday because we were late in getting the homework up.
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).
3 As always, the faster the better.