Use Djikstra's algorithm with an optimised version of the priority queue. Assume the graph has nodes 0..V-1.
The priority queue will consist of an array Arr[0..D] (an array with indices between 0 and D inclusive) of doubly-linked lists of nodes, together with an index i indicating that the priority of all nodes in the array are of distance at least i from the starting node, and an array location[0..V - 1], where the value of location[node] is the doubly-linked list node in Arr containing node, or null if there is no such node. We store a node in the list Arr[i] when we have found a path of length i from the start node to the node in question.
Adding a node to the priority queue which is not already there is O(1) - if we have a tentative distance s, then we add the node to the linked list Arr[s] and update location[node] accordingly. Note that if the priority is >D, we should actually refrain from adding the node to the priority queue entirely and be confident that we will later add it to the queue with a priority <= D.
Removing a given node from the priority queue is also O(1) - we can find its doubly-linked-list node in O(1) using location[node], delete that node from the doubly-linked-list, and set location[node] to null. We will need this operation when we change the priority of a node.
Finding and removing the minimal node is less trivial. We continually increment i until we find some i such that Arr[i] is not empty. We then remove a node which is found in Arr[i] from the priority queue (don't forget to update location[node] as well). The total number of incrementings done in the whole program is D, since we will change i from 0 to D one increment at a time. Ignoring the incrementings, the other work done in this process is O(1).
Note that this is ONLY valid because we can guarantee that once we remove a node with priority i, we will never add another node with priority <i into the priority queue. It also only works because we know that we could never actually remove anything added to the priority queue with priority > D, since we can only remove something from the priority queue when it has its finalised correct path length, which is <= D - therefore, it's unnecessary to add anything to the priority queue with priority > D. This follows from the general properties of Dijkstra's algorithm when the graph has positive edge weights, and from the fact that the graph's diameter is D.
So the algorithm will be O(V + E + D), as required.
