25-2 Shortest paths in epsilon-dense graphs

A graph G=(V,E)G = (V, E) is ϵ\epsilon-dense if E=Θ(V1+ϵ)|E| = \Theta(V^{1 + \epsilon}) for some constant ϵ\epsilon in the range 0<ϵ10 < \epsilon \le 1. By using dd-ary min-heaps (see Problem 6-2) in shortest-paths algorithms on ϵ\epsilon-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\text{INSERT}, EXTRACT-MIN\text{EXTRACT-MIN}, and DECREASE-KEY\text{DECREASE-KEY}, as a function of dd and the number nn of elements in a dd-ary min-heap? What are these running times if we choose d=Θ(nα)d = \Theta(n^\alpha) for some constant 0<α10 < \alpha \le 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 ϵ\epsilon-dense directed graph G=(V,E)G = (V, E) with no negative-weight edges in O(E)O(E) time. (Hint:\textit{Hint:} Pick dd as a function of ϵ\epsilon.)

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

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

a.

  • INSERT\text{INSERT}: Θ(logdn)=Θ(1/α)\Theta(\log_d n) = \Theta(1 / \alpha).
  • EXTRACT-MIN\text{EXTRACT-MIN}: Θ(dlogdn)=Θ(nα/α)\Theta(d\log_d n) = \Theta(n^\alpha / \alpha).
  • DECREASE-KEY\text{DECREASE-KEY}: Θ(logdn)=Θ(1/α)\Theta(\log_d n) = \Theta(1 / \alpha).

b. Dijkstra, O(dlogdVV+logdVE)O(d\log_d V \cdot V + \log_d V \cdot E), if d=Vϵd = V^\epsilon, then

O(dlogdVV+logdVE)=O(VϵV/ϵ+E/ϵ)=O((V1+ϵ+E)/ϵ)=O((E+E)/ϵ)=O(E). \begin{aligned} O(d \log_d V \cdot V + \log_d V \cdot E) & = O(V^\epsilon \cdot V / \epsilon + E / \epsilon) \\ & = O((V^{1+\epsilon} + E) / \epsilon) \\ & = O((E + E) / \epsilon) \\ & = O(E). \end{aligned}

c. Run V|V| times Dijkstra, since the algorithm is O(E)O(E) based on (b), the total time is O(VE)O(VE).

d. Johnson's reweight is O(VE)O(VE).