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?
Is it possible to come up with a graph instance that would force Dijkstra to perform a decrease key on every single edge?
algorithms;data structures;shortest path
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....