バックトラッキングで解いたら

http://okajima.air-nifty.com/b/2010/01/post-abc6.html
Lv3らしい。でしょうね・・30分ぐらい。

高校生で効率良く解いた方がおられた。
http://d.hatena.ne.jp/qnighy/20100111/1263191078

# coding: utf-8
import sys
m = sys.stdin.read().splitlines()

# backtracking
mstep = len(m)*len(m[0])
mpath = None
path = set()
push = lambda x: path.add(x)
pop = lambda x: path.remove(x)
def backtracking(x, y, step):
    global mstep,mpath
    if step >= mstep:
        return
    push((x,y))
    if m[x][y] == "G":
        if step < mstep:
            mstep = step
            mpath = path.copy()
    else:
        for dx,dy in [(-1,0), (0,-1), (+1,0), (0,+1)]:
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < len(m)) or not (0 <= ny < len(m[0])):
                continue
            if m[nx][ny] in " G" and not (nx,ny) in path:
                backtracking(nx, ny, step+1)
    pop((x,y))

sx,sy = None,None
for i in xrange(len(m)):
    for j in xrange(len(m[0])):
        if m[i][j] == "S":
            sx,sy = i,j
            break
backtracking(sx, sy, 0)

for i in xrange(len(m)):
    for j in xrange(len(m[0])):
        if (i,j) in mpath and not m[i][j] in "SG":
            sys.stdout.write("$")
        else:
            sys.stdout.write(m[i][j])
    sys.stdout.write("\n")

追記：
ダイクストラ法によるプログラム。バックトラックとくらべてやっぱりちょっと頭を使う。

# coding: utf-8
import sys

m = sys.stdin.read()

n = map(list, m.splitlines())
w,h = len(n[0]), len(n)

m = m.replace("\n", "")

wh = w*h
dist,prev,fix = [1e100]*wh, [None]*wh, [False]*wh

src = m.index("S")
dst = m.index("G")

def edgesfrom(u):
    edges = []
    if u % w !=    0 and m[u-1] != "*": edges.append((u, u-1))
    if u % w !=  w-1 and m[u+1] != "*": edges.append((u, u+1))
    if u     <  wh-w and m[u+w] != "*": edges.append((u, u+w))
    if u     >=    w and m[u-w] != "*": edges.append((u, u-w))
    return edges

dist[src] = 0
fix[src] = True
bound = set(edgesfrom(src))  # 囲みの境界にあるエッジを記憶する
while len(bound) != 0:
    d,u = min((dist[s]+1, t) for s,t in bound)
    fix[u],dist[u] = True, d
    bound = set(b for b in bound if b[1] != u)
    for u,v in edgesfrom(u):
        if not fix[v]:
            bound.add((u,v))
    for u,v in edgesfrom(u):
        d = dist[u] + 1
        if d < dist[v]:
            dist[v] = d
            prev[v] = u
# 経路を求める
u = prev[dst]
while not u is None:
    n[u/w][u%w] = '$'
    u = prev[u]
print "\n".join(map(lambda line: "".join(line), n))