# 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 $G = (V,E)$ 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 $s$, given an algorithm computing shortest paths from $s$ to any other vertex in $O(m + n \log n)$ time. The algorithm should output the following: either that the graph has a negative length cycle reachable from $s$, or the shortest path distances from $s$ to all the nodes $v \in V$.

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 $G = (V,E)$ be a directed acyclic graph with real-valued edge weights $w : E \to \mathbb{R}$. Design and analyze an algorithm that, given a vertex $s \in V$, find the length of the shortest path from $s$ to every other vertex (or $+\infty$ if there is no path) in $O(m+n)$ time.