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

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

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