Problems finding the shortest path in the matrix
I wrote part of the program but could not find how to proceed. This is my homework, and I've been working on it for ten days, and my time is about to run out. My program requirements are: a) get N as input by keyword. b) generate random integers between 1 and N * N c) fill the matrix with these integers I did it but couldn't get more.
The more => greedy approach for example, user enters 3 as input. and the program returns as a matrix
1 2 6
4 8 5
3 9 7
the shortest path - 1,2,6,5,7. another user example enters 4 as the input and return matrix of a program like
14 11 6 8
15 3 16 1
10 4 2 5
12 9 7 13
the shortest path can be 14,11,3,4,2,5,13,
and no cross steps are allowed along the way.
My code is below.
import java.util.*;
public class Challenge1 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("Enter a value for the matrix size.");
int length = input.nextInt();
int[][] x = randomMatrix(length);
for (int i = 0; i < x.length; i++) {
for (int j = 0; j < x[i].length; j++) {
System.out.print(x[i][j] + " ");
}
System.out.println();
}
}
public static int[][] randomMatrix(int n) {
Random r = new Random();
int[][] matrix = new int[n][n];
boolean[] trying = new boolean[n * n];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
matrix[i][j] = r.nextInt(n * n) + 1;
if (trying[matrix[i][j] - 1] == false)
trying[matrix[i][j] - 1] = true;
else {
while (trying[matrix[i][j] - 1] == true) {
matrix[i][j] = r.nextInt(n * n) + 1;
}
trying[matrix[i][j] - 1] = true;
}
}
}
return matrix;
}
}
source to share
Here's some python-ish pseudocode for the solution I mentioned in the comment. Let be shortestPath
an initially empty list, and shortestPathCost
be the sum of the weight of the shortest path found. Initially its meaning +infinity
. Both are globally visible.
Procedure exhaustiveSearch (currentCost, currentPath, endNode):
currentNode = currentPath.last
if currentNode == endNode and currentCost < shortestPathCost:
shortestPath = currentPath
shortestPathCost = currentCost
return
for each neighbouringNode of currentNode not in currentPath:
exhaustiveSearch (currentCost + neighbouringNode.cost,
currentPath + neighbouringNode,
endNode)
That's pretty much it. Parameters are copied by value. If you call it as such:
exhaustiveSearch(0, [firstNode], endNode);
shortestPath
and shortestPathCost
will hold one of the shortest paths in the grid. Obviously, the solution is at a slightly higher level than Java
, but it should be simple to implement.
source to share