# Is it possible to come up with a graph instance that would force Dijkstra to perform a decrease key on every single edge?

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?

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