Single-source shortest path problem with diameter

Question

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)$?

**Update **

From https://stackoverflow.com/questions/66570124/single-source-shortest-path-in-a-graph-with-positive-weights-and-diameter-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

• D.W.: Where did you encounter this task? Please credit the source of all copied material: see cs.stackexchange.com/help/referencing. This might help us give you answers that are a better match to the context where you encountered it, and helps others with a similar question find this via search.

Answer 1

Instead of a min-heap use an array of $D +2$ lists indexed from 0 to $D+1$. The $i$th list contain vertices whose distance to the source equals $i$ except for the last one which contains vertices with unbounded distance.

Iterate over this array from 0ドル$ to $D$ and for each list, while not empty choose the head of the list as the vertex whose incident edges are to be relaxed in this iteration (the vertex with min distance to the source) and remove this element from this list.

To ensure updates add an array of $n$ pointers such that each vertex points to its occurance in the lists .

It is easy to see that updates run in constant time, hence we get $O(m)$ for updates over all edges. Since we iterate over empty lists and each vertex only once in the array we have amortized running time $O(n+m)$ for iterations.