25-2 Shortest paths in epsilon-dense graphs

A graph \(G = (V, E)\) is \(\epsilon\)-dense if \(|E| = \Theta(V^{1 + \epsilon})\) for some constant \(\epsilon\) in the range \(0 < \epsilon \le 1\). By using \(d\)-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 \(\text{INSERT}\), \(\text{EXTRACT-MIN}\), and \(\text{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 = \Theta(n^\alpha)\) for some constant \(0 < \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)\) with no negative-weight edges in \(O(E)\) time. (\(\textit{Hint:}\) Pick \(d\) 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)\) 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 \(\epsilon\)-dense directed graph \(G = (V, E)\) that may have negative-weight edges but has no negative-weight cycles.

a.

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

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

\[ \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|\) times Dijkstra, since the algorithm is \(O(E)\) based on (b), the total time is \(O(VE)\).

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

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用