I'm working on a maze solving program, and was curious if anyone had or knew of any good shortest path problem algorithms?

I was planning to have my program search the maze for all intersections, eliminate dead ends, eliminate loops that only concern one intersection, and loops that concern two intersections (reason why later on) then use all the remaining intersections as vertices for a shortest path algorithm. The weights on edges between the vertices were going to be the actual "traveling" distance in the maze between each intersection, so it wouldn't be inaccurate in trying to get actual distances between intersection.

Since dead ends by nature cannot lead to the exit, they'll be omitted, and the program will fill in that area, acting as if it were never there, then recheck the intersection that lead to it (in the event that the intersection would now have only two "exits" to it, and it no longer qualify as an intersection, but a hallway). Loops that concern one intersections cannot make a line, using only one point, so they'll be treated much like dead ends, and will be omitted, then will recheck the intersection that lead them to the loop. Loops that concern two intersections will lead to unnecessary confusion, by allowing there to be two possible distances between two points, so the longer of them will be omitted, and both intersections involved will be rechecked.

After the maze has been successfully converted, it will begin with it's shortest path algorithm. I know I could always have it recursively check each vertex, with each edge, but I was wondering if there was a faster algorithm to use instead of this. After checking the wiki, it seemed that all of the algorithms posted so far, seem to only check the lowest weighted paths from one vertex to another, or other local methods that don't have much hold on the whole of the graph.

For instance, Dijkstra's algorithm checks the shortest distance from the current vertex, and in the example shown, takes the path (from point A (vertex 1) to point B (vertex 5)) of 1,2,3,6,5 with a total distance of 7+10+2+9=28, where as it could have taken a number of paths that have a shorter total distance than this (the fastest of which I found after a cursory glance being 1,3,6,5 being 9+2+9=20)

Is there a more logical way for me to have it find the lowest value path, or will I have to have it guess and check for the lowest distance among all possible distances, from it's list of possible paths that actually reach the exit.

P.S. The main reason I asked instead of simply implementing the recursive check, was because I had remembered seeing a problem much like this from an AP Statistics student's homework they showed me, and figured there just might then be a logical or mathematical process to find the fastest possible path.

OK, I just finished an intensive semester-long algorithms, so I have the whole set of solutions for you. There's two main classes of algorithms that are applicable: APSP (All Pairs Shortest-Paths), especially Floyd-Warshall's, which operates in O(n^3) time; and SSSP (Single-Source Shortest-Paths), most notably Dijikstra's, which you already know. You should also be aware of how each handles cycles, since you mentioned that. I think that Dijikstra's (or another SSSP) algorithm is your best choice for a maze checker/solver, but I'll certainly re-post with some more detailed information after I start my laundry.

It may not be strictly related to what you're doing here, but the Wolfram Blog had a few maze-solving applications outlined at the end of December:
http://blog.wolfram.com/2010/12/21/the-battle-of-the-marlborough-maze-at-blenheim-palace-continues/

The approach there was basically just doing some image processing to convert the image of the maze to a graph, then find the shortest path. I'm sure they don't specify what algorithm Mathematica uses internally for that, but Djikstra's Algorithm would certainly do the job, as we've all noted.

This is the main thing I see that could go wrong with using SSSP, other than the inefficiency seen on the wiki for Dijkstra's Algorithm.

Can you tell me what the problem is based on that diagram so I can demonstrate why it's not a problem?

Using SSSP, it would go away from the designated destination point, instead of towards it, because it's going to the closest vertex to it. From point A, it'd go to the vertex 2 away, instead of 14, then to the one 4 away, then to the one 5 away, etc., until it would go elsewhere in the maze. It would then have used all the points leading to point B, so it would no longer be able to reach point B.

But what you're missing is that it deals with the successively-shortest paths from the original source point, not edges, so it will eventually take care of that edge and find that 14 is the shortest-path distance to B.

When you have a free moment, could you make some example code? You lost me with that.

From Wikipedia:


Let's consider your diagram. We'll call the two labeled points A and B, and the remaining points, counting nearest to A first, C, D, E, and F. Please be careful to note that Dijikstra's works on directed edges. I've taken all edges as pointing towards B and/or away from A (that is, your graph consists of e ∈ E = {A,B,C,D,E,F}; v ∈ V = {AB, AC, CB, CD, DB, DE, EB, EF, FB, F?}).



1. Set A as current and source; minimum distance source->A is zero (trivial case).
2. Explore all its neighbors. Minimum distance source->B goes from infinity to 14. Minimum dist source->C goes from infinity to 2.
3. Next-closest vertex to source is C (dist 2). Set C as current.
4. Explore C's neighbors. Min dist source->B is 14, less than or equal to source->C->B dist of 14. No update. Min dist source->D goes from infinity to 2+4=6.
5. Next-closest vertex to source is D (dist 6). Set D as current.
6. Explore D's neighbors. Min dist source->B is 14, less than or equal to source->D->B dist of 20. No update. Min dist source->E goes from infinity to 6+5=11
7. Next-closest vertex to source is E (dist 11). Set E as current.
8. Explore E's neighbors. Min dist source->B is 14, less than or equal to source->E->B dist of 21. No update. Min dist source->F goes from infinity to 11+3=14.
9. Next-closest vertex to source is B or F (dist 14). Set B as current.
10. B has no outbound edges.
11. Next closest vertex to source is F (dist 14). Set F as current.
12. Explore F's neighbors. Min dist source->B is 14, less than or equal to source->F->B dist of 26. No update. [Explore "<12" edge(s)
13. (Algorithm continues)

I hope that made sense; it's important to be able to pretend to be the algorithm to be able to implement it well.

Alright, 7 hours of thought later, I think I understand it now, but I still am having difficulty explaining it. Although it keeps moving to the closest point to it, it keeps using the points around the current to find a faster route from source, correct?

Also another question, suppose that the two closest points to the current point were of equal value, which should it choose, or is that something not covered by the algorithm, and that should be up to the program/person using the algorithm?

Also, any tips on implementing this to code? I'm falling short on ideas for having it keep track of the distance from source through certain points for each path, but I'll keep thinking about it.

Well, I think a better way to think about it is that it moves to the next closest point to the original source on each iteration, then updates the distances from the source to each of that vertex's children/neighbors. For two points of equal distance, there's no criteria on which to choose. Finally, for your last question: all you need to track is, for each vertex, the known shortest distance from the source to that vertex, which as I mentioned on IRC you initialize to infinity. :_)

You could also consider A*, but Djikstra is probably a good place to start.

oh dear, I just finally got Dijkstra's, I don't want to try another for the next week or so.

But who knows, perhaps if I do understand a few of the algorithms, then I may add an option for the user to choose which algorithm they would like to use for solving the maze.

Semi-necrobump. So how's your understanding of Dijikstra's going? Do you feel you have a good handle on it now? What's happening with this project in general; will it get a project thread?

I feel I have a good handle on the algorithm now. I'll probably post some code soon of what I have, but I have yet to finish all the code that trims down the maze's unneeded paths, and format the maze into a proper syntax for the algorithm, so I'm going to finish that first before posting anything.

As of now, it will display the maze, find the intersections and record their coordinates into list 2 with the first point in the list being the source in the upper left hand corner, and the second in the list being the end point in the lower right hand corner. It will then follow each intersection until it hits another intersection or a dead end, then pause the program. It has sub-methods for (1) following a path, with an option for (2) deleting the path, (3) recalibrating an cell so it doesn't lead into surrounding cells that don't lead to it (this makes it so it doesn't have to worry about intersections leading into deleted paths), and (4) redisplaying a given cell.

I'm aiming to have the final product (1) use a GUI so you draw the maze as opposed to typing in values for each cell, (2) use inputted source and destination cells instead of predetermined corners (likely using a negative value so it knows where point A and B are, and just picking one of them to be the source instead of being specified which is), (3) using multiple algorithms to solve the maze, as I've said before I was considering (this going under the assumption that I can comprehend and implement multiple algorithms to use for maze solving), and lastly and least importantly (4) having an option so it displays what checks it's currently doing, and showing the current path throughout the maze so the user doesn't become impatient with the wait that may arise.

I'm fairly certain there were a few other things I wanted to add to this, but I'll add them when I remember them.

Please post if you have anything else to say about this, or if you have any other algorithms you think would work nicely with this. From what I saw on the wiki, the only thing I can think of that I shouldn't have to worry about needing in an algorithm to work with this is using negative values, since mazes can't have negative values for distances between intersections.

Definitely not optimal, but just for fun:

While 1
For(A,1,61
For(B,1,93
If 2<(pxltest(A+1,B)+pxltest(A-1,B)+pxltest(A,B+1)+pxltest(A,B-1
pxlon(A,B
End
End
End

Guaranteed to solve all mazes on the graph screen that use 1px corridors. Pretty sure this solution is the smallest in terms of codesize.

NOTE: have not actually tested this, just coded in my mind as I typed, though I'm 99% sure it works.

That's also going to "follow" every single dead end, though, and it doesn't extract any useful information about the maze's solution. I see what you did there, though; that's an interesting approach.

Mufin: As you state, negative cycles are a problem for shortest-path algorithms, but also as you state, that's not a concern here.

Kerm: It just fills in all dead-end routes, leaving the solution the only route remaining. If you wanted "information" about the mazes solution, as in, which turns to take, it's trivial to follow that one remaining path.

It's also going to fill in all the paths from the start to the first intersection and the last intersection to the end, etc, unless you're somehow assuming that the start and end are in 3x3 spaces or on the edges, which it suddenly occurs to me you probably are.

I'm assuming the maze has an entrance and an exit which are on the edges of the screen.