2
$\begingroup$

From the analysis of Dijkstra there is a $O(mlogn)$ factor that assumes we do a decreasekey for every single edge of the given input graph.

However I find it hard to come up with an instance that can actually require this. All you have to do create the edges and then add the weights in a way that would induce a large number of decrease keys.

Is there any known way of doing that?

$\endgroup$

1 Answer 1

4
$\begingroup$

Yes!

A bit convoluted example is the following:

Suppose you have $n+1$ nodes and you run djikstra from $a_{0}$ Let $A=[a_{0},a_{1},a_{2}.....,a_{n}]$ the final result of the algorithm(i.e the nodes of the graph sorted by their distance from $a_{0}$)

We will now create a graph which will require every edge to be updated:

First of all add edge $e_{i}=(a_{i} , a_{i+1}) $ with $cost(e_{i})=0$ for every $i<n$

Let $M$ be a really Big Value.

For every $i<n$ and $j>i+1$ add the edge $e_{ij}=(a_{i},a_{j})$ with $cost(e_{ij})=M-i$

At every step $i$ of the algorithm ALL values of the nodes will be updated.

ex. $M=100, n+1=5$

Distance matrix for $A$

step 0: [-,0,100,100,100,100]

step 1: [-,-,0 , 99, 99 ,99] and so on....

$\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.