Ideal value of d in a d-ary heap for Dijkstra's algorithm
Please note that $ m \leq n(n-1)/2 $, thus $m/n &lt; n/2$. So the example $m=3, n=1$ does not happen.

First, the article clearly claims that this improvement is achieved whenever $ m $ is larger than $ n $,


  By using a $d$-ary heap with $d = m/n$, ..., an improvement over the O(m
  log n) running time of binary heap versions of these algorithms
  whenever the number of edges is significantly larger than the number
  of vertices.


Secondly, the article claims that $d$ must create a balance between $m$ and $n$ in order to improve the running time,


  By using a $d$-ary heap with $d = m/n$, the total times for these
  two types of operations may be balanced against each other...


Generally, we need $n$ min-extract and $m$ decrease-key operations. In the case of $d=2$, each of these operations takes $O(\log n)$ time. However, when you increase $d$, the decrease-key operation becomes faster, but min-extract can become slower. Because, within each min-extract, we also need to run min-heapify that depends on the number of children of the parent in each level.

In the extreme case, if you consider $ d=n $ then $m \log_n n &lt; m \log_{m/n} n$, but the running time won't be better in practice. Because you need at most $ n $ min-extract operations, each includes a min-heapify. Therefore, you need $ n $ min-heapify operations, that will cost $ O(n) $ in this case (because $d=n$ and there are $n$ numbers in the next level of your tree). Thus the running time of your algorithms becomes $O(n^2)$ ($n$ times running min-heapify).