(The program should be written in Java) Consider the problem of finding the shor
ID: 3794555 • Letter: #
Question
(The program should be written in Java)
Consider the problem of finding the shortest path between two points on a place that has convex polygonal obstacles as shown in the following figure. This is an idealization of the problem that a robot has to solve to navigate in a crowded environment.
Write a program to implement A* search to find the shortest path from the start point to the goal. Make sure your program generates the shortest path on any map, not just this particular one.
Details about the program:
• Input: a text file containing the coordinates of start point, goal point, and vertices of all polygons. For example, an input text file map1.txt contains:
1, 3 ! (x, y) of the start point
34, 19 ! (x, y) of the goal point
0, 14; 6, 19; 9, 15; 7, 8; 1, 9 ! vertices of the 1st polygon, separating by semicolons
2, 6; 17, 6; 17, 1; 2, 1 ! vertices of the 2nd polygon, separating by semicolons
• Make sure your program can be compiled using the following command: javac aixxx.java
• Your program will be tested on osprey as follows: java aixxx input_map_file.txt input_map_file: a text file similar to map1.txt
• Output: a sequence of coordinates showing the shortest path from the start point to the goal point.
Example input txt file:
1, 3
34, 19
0, 14; 6, 19; 9, 15; 7, 8; 1, 9
2, 6; 17, 6; 17, 1; 2, 1
12, 15; 14, 8; 10, 8
14, 19; 18, 20; 20, 17; 14, 13
18, 10; 23, 6; 19, 3
22, 19; 28, 19; 28, 9; 22, 9
25, 6; 29, 8; 31, 6; 31, 2; 28, 1; 25, 2
31, 19; 34, 16; 32, 8; 29, 17
Explanation / Answer
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;
public class Shortest_Path_to_AllVertex
{
private int distances[];
private Set<Integer> settled;
private Set<Integer> unsettled;
private int number_of_nodes;
private int adjacencyMatrix[][];
public Shortest_Path_to_AllVertex(int number_of_nodes)
{
this.number_of_nodes = number_of_nodes;
distances = new int[number_of_nodes + 1];
settled = new HashSet<Integer>();
unsettled = new HashSet<Integer>();
adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];
}
public void shortestPath(int adjacency_matrix[][], int source)
{
int evaluationNode;
for (int i = 1; i <= number_of_nodes; i++)
for (int j = 1; j <= number_of_nodes; j++)
adjacencyMatrix[i][j] = adjacency_matrix[i][j];
for (int i = 1; i <= number_of_nodes; i++)
{
distances[i] = Integer.MAX_VALUE;
}
unsettled.add(source);
distances[source] = 0;
while (!unsettled.isEmpty())
{
evaluationNode = getNodeWithMinimumDistanceFromUnsettled();
unsettled.remove(evaluationNode);
settled.add(evaluationNode);
evaluateNeighbours(evaluationNode);
}
}
private int getNodeWithMinimumDistanceFromUnsettled()
{
int min;
int node = 0;
Iterator<Integer> iterator = unsettled.iterator();
node = iterator.next();
min = distances[node];
for (int i = 1; i <= distances.length; i++)
{
if (unsettled.contains(i))
{
if (distances[i] <= min)
{
min = distances[i];
node = i;
}
}
}
return node;
}
private void evaluateNeighbours(int evaluationNode)
{
int edgeDistance = -1;
int newDistance = -1;
for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++)
{
if (!settled.contains(destinationNode))
{
if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)
{
edgeDistance = adjacencyMatrix[evaluationNode][destinationNode];
newDistance = distances[evaluationNode] + edgeDistance;
if (newDistance < distances[destinationNode])
{
distances[destinationNode] = newDistance;
}
unsettled.add(destinationNode);
}
}
}
}
public static void main(String... arg)
{
int adjacency_matrix[][];
int number_of_vertices;
int source = 0;
Scanner scan = new Scanner(System.in);
try
{
System.out.println("Enter the number of vertices");
number_of_vertices = scan.nextInt();
adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
System.out.println("Enter the Weighted Matrix for the graph");
for (int i = 1; i <= number_of_vertices; i++)
{
for (int j = 1; j <= number_of_vertices; j++)
{
adjacency_matrix[i][j] = scan.nextInt();
if (i == j)
{
adjacency_matrix[i][j] = 0;
continue;
}
if (adjacency_matrix[i][j] == 0)
{
adjacency_matrix[i][j] = Integer.MAX_VALUE;
}
}
}
System.out.println("Enter the source ");
source = scan.nextInt();
Shortest_Path_to_AllVertex sp = new Shortest_Path_to_AllVertex(
number_of_vertices);
sp.shortestPath(adjacency_matrix, source);
System.out.println("The Shorted Path from " + source
+ " to all other nodes are: ");
for (int i = 1; i <= sp.distances.length - 1; i++)
{
System.out.println(source + " to " + i + " is "
+ sp.distances[i]);
}
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");
}
scan.close();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.