# Single source shortest paths problem

Assume a directed graph with positive integer values for edge weights. Also, we know that the cost of the longest shortest path is $$K$$.

The objective is to construct an algorithm that finds the shortest paths from a source node $$s$$ to all the other nodes in $$(K + V + E)$$ time.

I cannot see how the cost of the longest shortest path can be used by the algorithm to produce the required shortest paths. Can someone provide me with a hint?

• Possible duplicate of this question asked one day earlier by a different user. However, the present question is more detailed (e.g. mentions integer weights), so I'm not necessarily in favour of closing. Nov 23, 2020 at 20:42

Here are a few hints. I suggest you think about each hint before moving on to the next one, but it's really up to you.

Hint 1:

The distance from $$s$$ to an arbitrary node can only take on $$K + 1$$ different values.

Hint 2:

Make a modification of Dijkstra's algorithm that runs in $$O(K + V + E)$$ time and uses $$O(K + V + E)$$ memory.

Hint 3:

Can you think of an algorithm to sort $$n$$ integers in the range $$\{0,1,\ldots,k\}$$ using $$O(n + k)$$ time and $$O(n + k)$$ memory?