3
$\begingroup$

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: enter image description here

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 enter image description here

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Maxfield Jan 28 at 10:14
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Jan 28 at 12:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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