3
$\begingroup$

Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$.

Then for a fixed $|V|$, what is the largest possible ratio between this runtime and the runtime of Dijkstra using a Fibonacci heap? Where knowing the Fibonacci heap: delete_min = $O(\log |V |)$, insert/decrease_key = $O(1)$ (amortized) and $|V|$ × delete_min + $(|V | + |E|) $ x insert $= O(|V|\log|V|+|E|)$.

On the other hand, d-ary heap implementation : delete_min = $O(\dfrac{d \log|V|}{\log d})$, insert/ decrease_key =$O(\dfrac{\log|V|}{\log d}$), and |V | × delete_min + (|V | + |E|) × insert = $O( (|V|·d+|E|)\dfrac{ \log|V|}{\log d})$.

As trying to follow a provide solution, but I am not sure why it reduces to $O(\dfrac{\log|V|}{\log |E|/|V|})$, in the case 1 where |E| dominates, so Dijkstra with Fibonacci heap is $O(|E|)$. How can we get the ratio as $O(\dfrac{\log|V|}{\log |E|/|V|})$ while Dijkstra with d-ary heap is $O( (|V|·d+|E|)\dfrac{ \log|V|}{\log d}$)?

enter image description here

$\endgroup$
1
$\begingroup$

The crux is right there in the first paragraph of the post.

Let's say that Dijkstra’s algorithm with the priority queue using a $d$-ary heap. We can achieve the best runtimes for the algorithm with $d$ being $\sim |E|/|V|$.

As you have pointed out, the time-complexity of Dijkstra with $d$-ary heap is $O\left((|V|\cdot d+|E|)\dfrac{ \log|V|}{\log d}\right)$. Substituting $|E|/|V|$ for $d$, we see the best time-complexity of Dijikstra with d-ary heap is $O\left((2|E|)\dfrac{\log|V|}{\log|E|/|V| }\right)=O\left(\dfrac{|E|\log |V|}{\log |E|/|V|}\right)$.

In the case 1 where $|E|$ dominates, the ratio of the best time-complexity of Dijkstra with $d$-ary heap to $O(|E|)$, the time-complexity of Dijkstra with Fibonacci heap is $\dfrac{\log|V|}{\log |E|/|V|}$ (ignoring some constant factor), which takes its maximum value when $|E|$ takes its minimum value, $|V|\log |V|$. Hence we get the ratio $\dfrac{\log|V|}{\log\log|V|}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.