Homework 5

Due Monday, February 3 at 5:00 PM. Please refer to the homework policy here.

  1. Chapter 5 exercise 25 ("racetrack") in Jeff's notes.

  2. Let be a directed weighted graph with edge lengths, where all of the edge lengths are positive except two of the edges have negative lengths. Given a fixed vertex , given an algorithm computing shortest paths from to any other vertex in time. The algorithm should output the following: either that the graph has a negative length cycle reachable from , or the shortest path distances from to all the nodes .

    Hint: First solve the case where there is only a single negative length edge. Handling just one negative length edge still gets partial credit.

  3. Let be a directed acyclic graph with real-valued edge weights . Design and analyze an algorithm that, given a vertex , find the length of the shortest path from to every other vertex (or if there is no path) in time.