CODEWITHSUNDEEP
javagraphshortest-pathmaze
Zieklecknerizer
Zieklecknerizer

Reputation: 275

shortest path through a maze

I am working on a project that i must traverse a maze using the left-hand rule and based upon the intersections the program comes upon i need to create a node to connect to a graph that I will then determine the shortest path. The goal is for the program to run through the maze then close out the program and read from a file that contains the graph and determines the shortest path to the finish. what i have done is i can traverse the maze using the left-hand rule. what im thinking to do is create a node when i find the intersection and there after every time the program moves i increase the cost of that path by one. on a side note do you need to have an adjacency matrix when use dijkstra's algorithm?

Upvotes: 2

Views: 2228

Answers (1)

Dagg Nabbit
Dagg Nabbit

Reputation: 76736

Try something like this, it should work:

0 - create an empty "solution path" stack of location objects.

1 - if current position is maze exit, return "solution path" stack.

2 - wall in front? turn left and repeat 2, else continue to 3.

3 - if current position is at top of "solution path" stack, 
       pop it off of the stack
       else push it onto the stack 

4 - move forward.

When you're checking the top of the stack for the current position, you might need to check the element just before the very last one, since the last one will be the position you just left.

Upvotes: 2

Related Questions