この問題。

maze = ["**************************",
        "*S* *                    *",
        "* * *  *  *************  *",
        "* *   *    ************  *",
        "*    *                   *",
        "************** ***********",
        "*                        *",
        "** ***********************",
        "*      *              G  *",
        "*  *      *********** *  *",
        "*    *        ******* *  *",
        "*       *                *",
        "**************************"]
solution = []
start    = ()
goal     = () 
max = (len(maze)-2) * (len(maze[0])-2)

for (h,line) in enumerate(maze):
    for (w,word) in enumerate(line):
        if   word == 'S': start = (h,w)
        elif word == 'G': goal  = (h,w)

checked = [start]

def add_route(sols):
    newroute = []
    for sol in sols:
        (h,w) = sol[-1]
        if ((h+1,w) not in checked) and maze[h+1][w] != '*':
            nr = list(sol)
            nr.append((h+1,w))
            checked.append((h+1,w))
            newroute.append(nr)
        if ((h-1,w) not in checked) and maze[h-1][w] != '*':
            nr = list(sol)
            nr.append((h-1,w))
            checked.append((h-1,w))
            newroute.append(nr)
        if ((h,w+1) not in checked) and maze[h][w+1] != '*':
            nr = list(sol)
            nr.append((h,w+1))
            checked.append((h,w+1))
            newroute.append(nr)
        if ((h,w-1) not in checked) and maze[h][w-1] != '*':
            nr = list(sol)
            nr.append((h,w-1))
            checked.append((h,w-1))
            newroute.append(nr)
    return newroute

def check_goal(sols):
    for sol in sols:
        if sol[-1] == goal:
            print draw_sol(sol)
            exit

def draw_sol(sol):
    solved_maze = ''
    for (h,line) in enumerate(maze):
        for (w,word) in enumerate(line):
            if (h,w) in sol[1:-1]:
                solved_maze += '$'
            else:
                solved_maze += word
        solved_maze += '\n'
    return solved_maze

sols = [[start]]

for i in range(max):
    sols = add_route(sols)
    check_goal(sols)

ちょっと長い

$ python maze.py
**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

ダイクストラ法とA*アルゴリズムの違いをあとで読む