## Introduction

See the general rules about assignments in this course.

**DUE**: 2016-11-25, 08:00 in the assignment box.

## Questions

Based on an exercise from Jeff Erickson.

Let `G = (V, E)`

be a directed graph with weighted edges; edge weights could be positive, negative,
or zero.

Describe an algorithm that constructs a directed graph

`H = (V' , E' )`

with weighted edges, where`V' = V ∖ {v}`

, and the shortest-path distance between any two nodes in`H`

is equal to the shortest-path distance between the same two nodes in`G`

, in`O(|V|²)`

time.*Hint*, think about replace two edge paths through`v`

with edges.Now suppose you know all shortest-path distances in

`H`

. Describe an algorithm to compute the shortest-path distances from`v`

to every other node, and from every other node to`v`

, in the original graph`G`

, in`O(|V|²)`

time.Combine the above results into all-pairs shortest path algorithm that runs in

`O(|V|³)`

time. (The resulting algorithm is not the same as Floyd-Warshall!)