This is an assignment that involves developing a program for solving a problem that is essentially Problem 4 of Homework 2.
We are given a set of points in the plane as a list, pointList , a source point src and target point trg . A man wishes to travel from src to trg , but he will be able to travel directly from point a to point b only if the Euclidean distance between them is at most a given parameter bound .
In general, then, his path from src to trg will consist of a sequence of intermediate points from pointList . Our task in this assignment is to write a Java program that will find a path with the smallest number of intermediate points. The method should take as input src , trg , pointList , and bound , and print the number of intermediate stops in the best path. If no feasible path exists, it should print that information. You can add your method to this file and test it using the input generated there. The program should be efficient in terms of running time -- for this assignment, that just means it should terminate within a few seconds when the number of points in pointList is of the order of 10000, as is the case with the way the data is currently generated.
The overall approach to follow is to construct a graph whose vertices correspond to the points, and whose edges correspond to pairs of points that are apart by at most bound. In this graph, we perform a breadth-first-search starting at src.
You have to submit the file containing the program source to a dropbox called Homework3 on ICON.