1
$\begingroup$

Can somebody can help me with this problem:

I have to calculate the minimum distance from a source node $s$ for undirected and connected graphs $G = ( V, E)$ with weights on the arcs belonging to the set $\{ 1, 2, . . . , k \}$, where $k$ is a fixed integer.

Implement Dijkstra's algorithm taking advantage of the peculiarity of these graphs so that the minimum distances to be calculated in $O ( k | V | + | E |)$.

I've no idea how to solve this problem. I don't need the specific code , but I need an algorithmic idea . Thanks in advance :)

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Hint: Use an array / list that you can do random access on as the priority queue instead of using a binary tree.

More hint: Suppose you have a super large array $q$. Now, whenever you "push" a value $i$ into the queue, place it into $q[i]$. Instead of popping the queue, you loop the queue from the smallest to largest index.

$\endgroup$
6
  • $\begingroup$ Dijkstra is usually $O(V \log E + E)$ right? What is the part that causes the $\log E$? $\endgroup$ Commented Nov 7, 2014 at 11:14
  • $\begingroup$ log E is caused by the update of the heap $\endgroup$ Commented Nov 7, 2014 at 11:20
  • $\begingroup$ @GabrieleSaturni Correct. Now, instead of using a heap, use an array. Update becomes $O(1)$. Read my "more hint". $\endgroup$ Commented Nov 7, 2014 at 11:23
  • $\begingroup$ ahhh okok now i understand , in this case i don't need the heap beacause the weights on the arcs is limited ...so it's sufficient do a loop from 1 to k and adding the nodes that have weight 1 to nodes that have weight k , of course , using the idea of dijkastra. Right?? $\endgroup$ Commented Nov 7, 2014 at 11:35
  • $\begingroup$ @GabrieleSaturni Nope, the loop must goes from $1$ through $kV$, since the longest possible path is of length $kV$. The insert is $O(1)$, but the loop is amortized $O(kV)$. $\endgroup$ Commented Nov 7, 2014 at 11:36

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.