Problem
Given a family {v1, v2, ..., vn} of n
"vertical" rays emanating from a point p, and a family
{h1, h2, ..., hm} of m "horizontal"
rays emanating from a point q, find the shortest path along the
rays from the point of intersection of v1 and
h1 to the point of intersection of vn and
hm.
- Click the left mouse button to add a vertical ray, SHIFT+Click to
add a horizontal ray, up to 10 rays in each family.
- The shortest path tree is drawn in yellow.
- Click and drag the endpoint of any horizontal and vertical ray to
see how the shortest path tree changes.
- Each ray has infinite extent, even though it is drawn as a line segment.
- SHIFT+Reload to restart the applet.
Source code:
ShortestPathApplet.java
GraphicsUtil.java
Shripad Thite
Last modified: Thu Nov 16 22:18:45 CST 2000