0
$\begingroup$

Given an undirected connected graph $G=(V,E)$ with positive weights, where $|V|>2009$, and each vertex is of degree of at most $10$. Give an efficient algorithm to find the $2009$ closest nodes to a given source vertex $s$ (with respect to edge weight).

Is it correct to say that Dijkstra's algorithm with Fibonacci heap will run in $\mathcal O(\log V)$?

Reasoning: Dijkstra's algorithm with Fibonacci heap runs in $\mathcal O(E+V\log V)$. the amount of vertices pulled out of the heap is $2009$, and the amount of key decreased is at most $2009*10$. Therfore the running time of Dijkstra's algorithm for this case is $\mathcal O(2009*10+2009 \log V)=\mathcal O(\log V)$

|cite|improve this question
$\endgroup$
  • $\begingroup$ Sorry, I meant the degree of a vertex, meaning the number of edges extending from it. $\endgroup$ – AmirB Jul 29 '16 at 22:01
  • 1
    $\begingroup$ No, the complexity of Dijkstra with Fibonacci heaps is O(|E| + |V| log |V|), that's an straightforward and valid answer, but is really what you want? $\endgroup$ – bones.felipe Jul 29 '16 at 22:29
  • $\begingroup$ The title is not very informative, then there is excersise and then not connected with description question about Dijkstra using Fibonacci heap, which cannot work faster than $|E|+|V|$ to read it. The complexity is $O((|V| + |E|) * log |V|)$. It is unclear to me what you are asking about. $\endgroup$ – Evil Jul 29 '16 at 22:31
  • $\begingroup$ Ok i added an explanation. I hope it is clearer. $\endgroup$ – AmirB Jul 29 '16 at 22:42
2
$\begingroup$

I do not think you can take $|V| = 2009$ because you are saying that $|V|>2009$, which means that in the best case $V = 2010$ but it does not say anything about the worst case (which is what big oh notation is about). So you cannot say that $|V|$ is constant as is implied in your question.

The correct process would be this: $O(|E| + |V| log |V|) = O(|V|*10 + |V| log |V|) = O(|V| + |V| log |V|)$
The only assumpution you can make is that $|E| = |V|*10 = |V|$. Remeber that you should only get rid of a variable in asymptotic notation if it is equal to a constant.

You can safely assume that $|E| = |V|*10$ because in the worst case every node will have 10 edges as stated in your question.

According to your reasoning dijkstra algorithm will only need overall 2009 extractions from the heap because you are looking for 2009 nodes close to $s$. That is not correct because is not possible in the algorithm to know beforehand which will be the exactly 2009 nodes that are close, say for example that the cheapest node $c$ has a shortest path of length $k$ and $k > 2009$, where $k$ is the number of nodes in the shortest path. Dijkstra algorithm will need to transverse the previous nodes and that will require more than 2009 operations in the heap because you have to process the nodes to reach node $c$ first.

Example:

Suppose you do not want to find 2009 closest nodes but 4 and that our source vertex is $7$, so following your question there should be overall 4 operations to get the 4 closest nodes. Given the following graph:

example

When you start the algorithm node $7$ is pushed into the heap, then nodes $0,1,2,3$ are pushed, in this case the number of times the nodes are pushed is the same number of times the nodes are popped from the heap (which may not be the case), now, as the algorithm proceeeds it will push nodes $4$ and $5$ until it reaches $6$ which in fact, is the closest node to $s$, if the path to node $6$ would have been longer a bigger number of push/pops would have been done in the heap. In a extreme case between node $3$ and $6$ there may be 90 nodes so that number of operations must be done in order to reach node $6$ which totally exceeds $4$ which is what is stated in your question.

The assumption that for every node $i$ that is extracted from the heap after any node $x$ follows that $d(s,i) > d(s,x)$ (where is $d(u,v)$ is the cost of the shortest path from $u$ to $v$) is not correct, because is possible that in the future you may insert another node into the heap that has a smaller distance, in fact that is what makes dijkstra algorithm actually compute optimal paths.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ yes, but the weights are all positive. that means that every time a vertex is taken out of the heap, all other vertices taken out after it are further away from s. that means that overall exactly 2009 extractions need to be made to get the 2009 closest nodes. $\endgroup$ – AmirB Jul 29 '16 at 23:17
  • $\begingroup$ Ok now I fully understood the question. But I still think that is not correct, you cannot say that there will be overall 2009 extractions from the heap, because you may need to relax more edges in the graph in order to obtain the shortest path from $s$ to all the nodes. For example, you can have a node that has a very small cost from $s$ but to reach it you may need to transverse all the nodes in the graph. Then you'll need $|V|$ extractions. $\endgroup$ – bones.felipe Jul 29 '16 at 23:31
  • $\begingroup$ I've updated the answer with a explanation according to the comment. If something is not clear please comment. $\endgroup$ – bones.felipe Jul 29 '16 at 23:40
  • $\begingroup$ @bones.felipe, I don't get why there can be more than 2009 extractions. because the weights are positive, when extraction #i is made, the node extracted is guaranteed to be the i closest to s. $\endgroup$ – AmirB Jul 30 '16 at 6:41
  • $\begingroup$ @AmirB I added an example to the answer. $\endgroup$ – bones.felipe Jul 30 '16 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.