Shortest path algorithm using Dijkstra with Fibonacci heap
I do not think you can take $|V| = 2009$ because you are saying that $|V|&gt;2009$, which means that in the best case $V = 2010$ but it does not say anything about the worst case (which is what big oh notation is about). So you cannot say that $|V|$ is constant as is implied in your question.

The correct process would be this: $O(|E| + |V| log |V|) = O(|V|*10 + |V| log |V|) = O(|V| + |V| log |V|)$
The only assumpution you can make is that $|E| = |V|*10 = |V|$. Remeber that you should only get rid of a variable in asymptotic notation if it is equal to a constant.

You can safely assume that $|E| = |V|*10$ because in the worst case every node will have 10 edges as stated in your question.

According to your reasoning dijkstra algorithm will only need overall 2009 extractions from the heap because you are looking for 2009 nodes close to $s$. That is not correct because is not possible in the algorithm to know beforehand which will be the exactly 2009 nodes that are close, say for example that the cheapest node $c$ has a shortest path of length $k$ and $k &gt; 2009$, where $k$ is the number of nodes in the shortest path. Dijkstra algorithm will need to transverse the previous nodes and that will require more than 2009 operations in the heap because you have to process the nodes to reach node $c$ first. 

Example:

Suppose you do not want to find 2009 closest nodes but 4 and that our source vertex is $7$, so following your question there should be overall 4 operations to get the 4 closest nodes. Given the following graph:



When you start the algorithm node $7$ is pushed into the heap, then nodes $0,1,2,3$ are pushed, in this case the number of times the nodes are pushed is the same number of times the nodes are popped from the heap (which may not be the case), now, as the algorithm proceeeds it will push nodes $4$ and $5$ until it reaches $6$ which in fact, is the closest node to $s$, if the path to node $6$ would have been longer a bigger number of push/pops would have been done in the heap. In a extreme case between node $3$ and $6$ there may be 90 nodes so that number of operations must be done in order to reach node $6$ which totally exceeds $4$ which is what is stated in your question.

The assumption that for every node $i$ that is extracted from the heap after any node $x$ follows that $d(s,i) &gt; d(s,x)$ (where is $d(u,v)$ is the cost of the shortest path from $u$ to $v$) is not correct, because is possible that in the future you may insert another node into the heap that has a smaller distance, in fact that is what makes dijkstra algorithm actually compute optimal paths.