Given that a graph G has only positive integer weights and its diameter D which is the greatest of the shortest paths among all pairs of vertices in G. For a single-source shortest path problem and design an algorithm runs in O(V+E+D) time.
As we know, in a single-source shortest path problem, we could use the Dijkstra Algorithm and it's running time is $O((V+E)log V)$ using a min-heap. So we can explore the minimum known distance. But the bottleneck is to insert and delete a min-heap structure.
With the information, how to reduce the running time to $O(V+E+D)$?
We continually increment i until we find some i such that Arr[i] is not empty.
This tells where does the $O(D)$ come from. But what I don't understand is why inserting and deleting take a constant amount of time if min-heap is still using. Or is it another data structure? Many thanks