find the shortest path between two points with obstacles
I need to find shortest path between two points in a grid given an obstacles.
Given a 2 dimensional matrix where some of the elements are filled
with 1 and rest of the elements are filled. Here X means you cannot
traverse to that particular points. From a cell you can either
traverse to left, right, up or down. Given two points in the matrix
find the shortest path between these points. Here S is the starting
point and E is the Ending point.
I came up with below code but I wanted to understand from the interview point of view what is the most efficient algorithm to solve this problem? Is there any better way to do this?
public static void main(String args) {
char matrix = {{'1','1','1', '1'},
{'1','S','1', '1'},
{'1','1','X', '1'},
{'1','1','1', 'E'}};
System.out.println(shortestPath(matrix));
}
public static int shortestPath(char matrix) {
int s_row = 0, s_col = 0;
boolean flag = false;
for (s_row = 0; s_row < matrix.length; s_row++) {
for (s_col = 0; s_col < matrix[0].length; s_col++) {
if (matrix[s_row][s_col] == 'S')
flag = true;
if (flag)
break;
}
if (flag)
break;
}
return shortestPath(matrix, s_row, s_col);
}
public static int shortestPath(char matrix, int s_row, int s_col) {
int count = 0;
Queue<int> nextToVisit = new LinkedList<>();
nextToVisit.offer(new int {s_row, s_col});
Set<int> visited = new HashSet<>();
Queue<int> temp = new LinkedList<>();
while (!nextToVisit.isEmpty()) {
int position = nextToVisit.poll();
int row = position[0];
int col = position[1];
if (matrix[row][col] == 'E')
return count;
if (row > 0 && !visited.contains(new int {row - 1, col}) && matrix[row - 1][col] != 'X')
temp.offer(new int {row - 1, col});
if (row < matrix.length - 1 && !visited.contains(new int {row + 1, col})
&& matrix[row + 1][col] != 'X')
temp.offer(new int {row + 1, col});
if (col > 0 && !visited.contains(new int {row, col - 1}) && matrix[row][col - 1] != 'X')
temp.offer(new int {row, col - 1});
if (col < matrix[0].length - 1 && !visited.contains(new int {row, col + 1})
&& matrix[row][col + 1] != 'X')
temp.offer(new int {row, col + 1});
if (nextToVisit.isEmpty() && !temp.isEmpty()) {
nextToVisit = temp;
temp = new LinkedList<>();
count++;
}
}
return count;
}
java algorithm data-structures breadth-first-search
asked Nov 20 at 7:23
flash
178117
add a comment |
I need to find shortest path between two points in a grid given an obstacles.
Given a 2 dimensional matrix where some of the elements are filled
with 1 and rest of the elements are filled. Here X means you cannot
traverse to that particular points. From a cell you can either
traverse to left, right, up or down. Given two points in the matrix
find the shortest path between these points. Here S is the starting
point and E is the Ending point.
I came up with below code but I wanted to understand from the interview point of view what is the most efficient algorithm to solve this problem? Is there any better way to do this?
public static void main(String args) {
char matrix = {{'1','1','1', '1'},
{'1','S','1', '1'},
{'1','1','X', '1'},
{'1','1','1', 'E'}};
System.out.println(shortestPath(matrix));
}
public static int shortestPath(char matrix) {
int s_row = 0, s_col = 0;
boolean flag = false;
for (s_row = 0; s_row < matrix.length; s_row++) {
for (s_col = 0; s_col < matrix[0].length; s_col++) {
if (matrix[s_row][s_col] == 'S')
flag = true;
if (flag)
break;
}
if (flag)
break;
}
return shortestPath(matrix, s_row, s_col);
}
public static int shortestPath(char matrix, int s_row, int s_col) {
int count = 0;
Queue<int> nextToVisit = new LinkedList<>();
nextToVisit.offer(new int {s_row, s_col});
Set<int> visited = new HashSet<>();
Queue<int> temp = new LinkedList<>();
while (!nextToVisit.isEmpty()) {
int position = nextToVisit.poll();
int row = position[0];
int col = position[1];
if (matrix[row][col] == 'E')
return count;
if (row > 0 && !visited.contains(new int {row - 1, col}) && matrix[row - 1][col] != 'X')
temp.offer(new int {row - 1, col});
if (row < matrix.length - 1 && !visited.contains(new int {row + 1, col})
&& matrix[row + 1][col] != 'X')
temp.offer(new int {row + 1, col});
if (col > 0 && !visited.contains(new int {row, col - 1}) && matrix[row][col - 1] != 'X')
temp.offer(new int {row, col - 1});
if (col < matrix[0].length - 1 && !visited.contains(new int {row, col + 1})
&& matrix[row][col + 1] != 'X')
temp.offer(new int {row, col + 1});
if (nextToVisit.isEmpty() && !temp.isEmpty()) {
nextToVisit = temp;
temp = new LinkedList<>();
count++;
}
}
return count;
}
java algorithm data-structures breadth-first-search
asked Nov 20 at 7:23
flash
178117
Dijkstra's Algorithm
– Sani Singh Huttunen
Nov 20 at 7:29
This is fine in principle (looks pretty much like BFS, right?). There are a few optimizations you could do: Try to avoid frequent allocation of new memory, store the visited flag in a fixed-size list rather than a hash set. For a more detailed review, go to Code Review.
– Nico Schertler
Nov 20 at 7:38
See this answer.
– John McClane
Nov 21 at 2:32
add a comment |
I need to find shortest path between two points in a grid given an obstacles.
Given a 2 dimensional matrix where some of the elements are filled
with 1 and rest of the elements are filled. Here X means you cannot
traverse to that particular points. From a cell you can either
traverse to left, right, up or down. Given two points in the matrix
find the shortest path between these points. Here S is the starting
point and E is the Ending point.
I came up with below code but I wanted to understand from the interview point of view what is the most efficient algorithm to solve this problem? Is there any better way to do this?
public static void main(String args) {
char matrix = {{'1','1','1', '1'},
{'1','S','1', '1'},
{'1','1','X', '1'},
{'1','1','1', 'E'}};
System.out.println(shortestPath(matrix));
}
public static int shortestPath(char matrix) {
int s_row = 0, s_col = 0;
boolean flag = false;
for (s_row = 0; s_row < matrix.length; s_row++) {
for (s_col = 0; s_col < matrix[0].length; s_col++) {
if (matrix[s_row][s_col] == 'S')
flag = true;
if (flag)
break;
}
if (flag)
break;
}
return shortestPath(matrix, s_row, s_col);
}
public static int shortestPath(char matrix, int s_row, int s_col) {
int count = 0;
Queue<int> nextToVisit = new LinkedList<>();
nextToVisit.offer(new int {s_row, s_col});
Set<int> visited = new HashSet<>();
Queue<int> temp = new LinkedList<>();
while (!nextToVisit.isEmpty()) {
int position = nextToVisit.poll();
int row = position[0];
int col = position[1];
if (matrix[row][col] == 'E')
return count;
if (row > 0 && !visited.contains(new int {row - 1, col}) && matrix[row - 1][col] != 'X')
temp.offer(new int {row - 1, col});
if (row < matrix.length - 1 && !visited.contains(new int {row + 1, col})
&& matrix[row + 1][col] != 'X')
temp.offer(new int {row + 1, col});
if (col > 0 && !visited.contains(new int {row, col - 1}) && matrix[row][col - 1] != 'X')
temp.offer(new int {row, col - 1});
if (col < matrix[0].length - 1 && !visited.contains(new int {row, col + 1})
&& matrix[row][col + 1] != 'X')
temp.offer(new int {row, col + 1});
if (nextToVisit.isEmpty() && !temp.isEmpty()) {
nextToVisit = temp;
temp = new LinkedList<>();
count++;
}
}
return count;
}
java algorithm data-structures breadth-first-search
asked Nov 20 at 7:23
flash
178117
I need to find shortest path between two points in a grid given an obstacles.
Given a 2 dimensional matrix where some of the elements are filled
with 1 and rest of the elements are filled. Here X means you cannot
traverse to that particular points. From a cell you can either
traverse to left, right, up or down. Given two points in the matrix
find the shortest path between these points. Here S is the starting
point and E is the Ending point.
I came up with below code but I wanted to understand from the interview point of view what is the most efficient algorithm to solve this problem? Is there any better way to do this?
public static void main(String args) {
char matrix = {{'1','1','1', '1'},
{'1','S','1', '1'},
{'1','1','X', '1'},
{'1','1','1', 'E'}};
System.out.println(shortestPath(matrix));
}
public static int shortestPath(char matrix) {
int s_row = 0, s_col = 0;
boolean flag = false;
for (s_row = 0; s_row < matrix.length; s_row++) {
for (s_col = 0; s_col < matrix[0].length; s_col++) {
if (matrix[s_row][s_col] == 'S')
flag = true;
if (flag)
break;
}
if (flag)
break;
}
return shortestPath(matrix, s_row, s_col);
}
public static int shortestPath(char matrix, int s_row, int s_col) {
int count = 0;
Queue<int> nextToVisit = new LinkedList<>();
nextToVisit.offer(new int {s_row, s_col});
Set<int> visited = new HashSet<>();
Queue<int> temp = new LinkedList<>();
while (!nextToVisit.isEmpty()) {
int position = nextToVisit.poll();
int row = position[0];
int col = position[1];
if (matrix[row][col] == 'E')
return count;
if (row > 0 && !visited.contains(new int {row - 1, col}) && matrix[row - 1][col] != 'X')
temp.offer(new int {row - 1, col});
if (row < matrix.length - 1 && !visited.contains(new int {row + 1, col})
&& matrix[row + 1][col] != 'X')
temp.offer(new int {row + 1, col});
if (col > 0 && !visited.contains(new int {row, col - 1}) && matrix[row][col - 1] != 'X')
temp.offer(new int {row, col - 1});
if (col < matrix[0].length - 1 && !visited.contains(new int {row, col + 1})
&& matrix[row][col + 1] != 'X')
temp.offer(new int {row, col + 1});
if (nextToVisit.isEmpty() && !temp.isEmpty()) {
nextToVisit = temp;
temp = new LinkedList<>();
count++;
}
}
return count;
}
java algorithm data-structures breadth-first-search
java algorithm data-structures breadth-first-search
asked Nov 20 at 7:23
flash
178117
asked Nov 20 at 7:23
flash
178117
edited Nov 27 at 2:19
asked Nov 20 at 7:23
flash
178117
asked Nov 20 at 7:23
flash
178117
asked Nov 20 at 7:23
flash
178117
178117
Dijkstra's Algorithm
– Sani Singh Huttunen
Nov 20 at 7:29
This is fine in principle (looks pretty much like BFS, right?). There are a few optimizations you could do: Try to avoid frequent allocation of new memory, store the visited flag in a fixed-size list rather than a hash set. For a more detailed review, go to Code Review.
– Nico Schertler
Nov 20 at 7:38
See this answer.
– John McClane
Nov 21 at 2:32
add a comment |
Dijkstra's Algorithm
– Sani Singh Huttunen
Nov 20 at 7:29
This is fine in principle (looks pretty much like BFS, right?). There are a few optimizations you could do: Try to avoid frequent allocation of new memory, store the visited flag in a fixed-size list rather than a hash set. For a more detailed review, go to Code Review.
– Nico Schertler
Nov 20 at 7:38
See this answer.
– John McClane
Nov 21 at 2:32
Dijkstra's Algorithm
– Sani Singh Huttunen
Nov 20 at 7:29
Dijkstra's Algorithm
– Sani Singh Huttunen
Nov 20 at 7:29
This is fine in principle (looks pretty much like BFS, right?). There are a few optimizations you could do: Try to avoid frequent allocation of new memory, store the visited flag in a fixed-size list rather than a hash set. For a more detailed review, go to Code Review.
– Nico Schertler
Nov 20 at 7:38
This is fine in principle (looks pretty much like BFS, right?). There are a few optimizations you could do: Try to avoid frequent allocation of new memory, store the visited flag in a fixed-size list rather than a hash set. For a more detailed review, go to Code Review.
– Nico Schertler
Nov 20 at 7:38
See this answer.
– John McClane
Nov 21 at 2:32
See this answer.
– John McClane
Nov 21 at 2:32
add a comment |
1 Answer
1
active
oldest
votes
The most efficient algorithm for this type of problem is BFS (Breadth-first search) if the cost for going from one point to another point is fixed. If the cost is variable but positive then you need to use Dijkstra Algorithm and if there have possibilities of negative cost, Bellman-Ford algorithm would be the right choice.
One more thing, to make yourself comfortable with this type of problem, one way is to solve this type of problem more. You will find this type of problem in this site.
answered Nov 20 at 10:25
Golam Rahman Tushar
666
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53388098%2ffind-the-shortest-path-between-two-points-with-obstacles%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
The most efficient algorithm for this type of problem is BFS (Breadth-first search) if the cost for going from one point to another point is fixed. If the cost is variable but positive then you need to use Dijkstra Algorithm and if there have possibilities of negative cost, Bellman-Ford algorithm would be the right choice.
One more thing, to make yourself comfortable with this type of problem, one way is to solve this type of problem more. You will find this type of problem in this site.
answered Nov 20 at 10:25
Golam Rahman Tushar
666
add a comment |
The most efficient algorithm for this type of problem is BFS (Breadth-first search) if the cost for going from one point to another point is fixed. If the cost is variable but positive then you need to use Dijkstra Algorithm and if there have possibilities of negative cost, Bellman-Ford algorithm would be the right choice.
One more thing, to make yourself comfortable with this type of problem, one way is to solve this type of problem more. You will find this type of problem in this site.
answered Nov 20 at 10:25
Golam Rahman Tushar
666
add a comment |
The most efficient algorithm for this type of problem is BFS (Breadth-first search) if the cost for going from one point to another point is fixed. If the cost is variable but positive then you need to use Dijkstra Algorithm and if there have possibilities of negative cost, Bellman-Ford algorithm would be the right choice.
One more thing, to make yourself comfortable with this type of problem, one way is to solve this type of problem more. You will find this type of problem in this site.
answered Nov 20 at 10:25
Golam Rahman Tushar
666
The most efficient algorithm for this type of problem is BFS (Breadth-first search) if the cost for going from one point to another point is fixed. If the cost is variable but positive then you need to use Dijkstra Algorithm and if there have possibilities of negative cost, Bellman-Ford algorithm would be the right choice.
One more thing, to make yourself comfortable with this type of problem, one way is to solve this type of problem more. You will find this type of problem in this site.
answered Nov 20 at 10:25
Golam Rahman Tushar
666
answered Nov 20 at 10:25
Golam Rahman Tushar
666
answered Nov 20 at 10:25
Golam Rahman Tushar
666
answered Nov 20 at 10:25
Golam Rahman Tushar
666
666
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53388098%2ffind-the-shortest-path-between-two-points-with-obstacles%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Dijkstra's Algorithm
– Sani Singh Huttunen
Nov 20 at 7:29
This is fine in principle (looks pretty much like BFS, right?). There are a few optimizations you could do: Try to avoid frequent allocation of new memory, store the visited flag in a fixed-size list rather than a hash set. For a more detailed review, go to Code Review.
– Nico Schertler
Nov 20 at 7:38
See this answer.
– John McClane
Nov 21 at 2:32