25-2 Shortest paths in epsilon-dense graphs
A graph G=(V,E) is ϵ-dense if ∣E∣=Θ(V1+ϵ) for some constant ϵ in the range 0<ϵ≤1. By using d-ary min-heaps (see Problem 6-2) 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. (Hint: Pick d as a function of ϵ.)
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.
a.
- INSERT: Θ(logdn)=Θ(1/α).
- EXTRACT-MIN: Θ(dlogdn)=Θ(nα/α).
- DECREASE-KEY: Θ(logdn)=Θ(1/α).
b. Dijkstra, O(dlogdV⋅V+logdV⋅E), if d=Vϵ, then
O(dlogdV⋅V+logdV⋅E)=O(Vϵ⋅V/ϵ+E/ϵ)=O((V1+ϵ+E)/ϵ)=O((E+E)/ϵ)=O(E).
c. Run ∣V∣ times Dijkstra, since the algorithm is O(E) based on (b), the total time is O(VE).
d. Johnson's reweight is O(VE).