A graph G = (V, E) is -dense if |E| = (V 1+ ) for some

A graph G = (V, E) is ∈-dense if |E| = Θ(V ^1+∈) for some constant ∈ in the range 0 < ∈ ≤ 1. By using d-ary min-heaps in shortest-paths algorithms on ∈-dense graphs, we can match the running times of Fibonacci-heap based algorithms without using as complicated a data structure.

a. What are the asymptotic running times for INSERT, EXTRACT-MIN, and DECREASE-KEY, as a function of d and the number n of elements in a d-ary min-heap? What are these running times if we choose d = Θ(n^α) for some constant 0 < α ≤ 1? Compare these running times to the amortized costs of these operations for a Fibonacci heap.

b. Show how to compute shortest paths from a single source on an ∈-dense directed graph G = (V, E) with no negative-weight edges in O(E) time. 

c. Show how to solve the all-pairs shortest-paths problem on an ∈-dense directed graph G = (V, E) with no negative-weight edges in O(VE) time.

d. Show how to solve the all-pairs shortest-paths problem in O(VE) time on an ∈-dense directed graph G = (V, E) that may have negative-weight edges but has no negative-weight cycles.