3
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Nov 23, 2020 at 20:42

1 Answer 1

0
$\begingroup$

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?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .