# Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue

we know the performance of Dijkstra's algorithm with binary heap is O(log |V |) for delete_min, O(log |V |) for insert/ decrease_key, so the overall run time is O((|V|+|E|)log|V|).

Now let's modify the Dijkstra to stop once it reaches T (Destination) from S(Start). The given performance is:

Understand that we don't need to explore the full G in the modified Dijkstra run. Can someone explain why it is the diamond shape(the 45 degree rotate of a perfect square)?

What does it means with the radios of |m|+|n|, (typo of radius ?)

What is m and n in this case? (m means vertices? n means edges?) seems to me that $$(|m|+|n|)^2$$ is half of the vertices and edges visited，which is half of the Diamond/Square. Then not sure how is it is computed.

added new pic for the additional questions

• Please add a url or reference to the original material in the question. – John L. Jan 24 '19 at 19:59
• Have you tried running the Dijkstra's algorithm in this situation? Please reach at least 13 nodes. – John L. Jan 24 '19 at 20:03

## 1 Answer

In the example, we can assume the start cell $$s$$ is the origin in a plane consisting of square cells with Descarte coordinates. That is, $$s$$ is $$(0,0)$$. The coordinate of destination cell, $$t$$ is $$(m,n)$$. The distance of any two cells is given by the taxicab geometry. That is, the distance between cells $$(p_1,p_2)$$ and $$(q_1,q_2)$$ is $$d((p_1,q_2),(q_1,q_2))=|p_1-p_2|+|q_1-q_1|$$ In particular, $$d(s,t)=|m|+|n|$$.

At the last step of running Dijkstra's algorithm with source cell $$s$$ when we visit cell $$t$$, all cells whose distance to $$s$$ is smaller than $$d(s,t)$$ must have been visited. Some of the cells whose distance to $$s$$ is $$d(s,t)$$ may have also been visited. If you color all cells that are no more than $$d(s,t)$$ away from $$s$$, you will get a diamond shape whose boundary cells $$(p,q)$$ are given by the following equations.

\begin{align} p+q = d(s,t) &\text{ where }p\ge0, q\ge0. \text{ This is the top right segment.}\\ p-q = d(s,t) &\text{ where }p\ge0, q\le0. \text{ This is the bottom right segment.}\\ -p+q = d(s,t) &\text{ where }p\le0, q\ge0. \text{ This is the top left segment.}\\ -p-q = d(s,t) &\text{ where }p\le0, q\le0. \text{ This is the bottom left segment.}\\ \end{align}

That diameter shape is, in fact, a circular disk with center $$(0,0)$$ and radius $$|m|+|n|$$ in the taxicab geometry. Yes, as you pointed out, "radios" should be "radius".

How many cells are there in the diamond shape? The diamond shape is actually a square the length of whose diagonals is $$2(|m|+|n|)$$. So its area is $$(2(|m|+|n|))^2/2=2(|m|+|n|)^2$$, which is about the number of cells in the it asymptotically.

Exercise. The exact number of cells in a disk with radius $$r$$ in the taxicab geometry is $$2r^2+2r+1$$. In particular, there are 13 cells in a disk with radius 2.

• Can you please point out why "The diamond shape is actually a square whose diagonal is 2(|m|+|n|)" or is is just the law? The diagonal of the square is the blue line, correct? Please see the the picture with the blue line. 2(|m|+|n|) seem like some line random as red line. – Maxfield Jan 28 '19 at 10:14
• Yes, one of the diagonals of the square is the blue segment. The other diagonal is the vertical segment through $s$. It is then law in taxicab geometry. That is, a circular disk with radius $r$ in the taxicab geometry is a square whose diagonals are $2r$ in the usual Euclidean geometry. – John L. Jan 28 '19 at 12:21