import heapq

data = [[ 4 ,   5 ,   3 ,   6 ,   7 ],
        [ 6 ,  10 ,  11 ,  15 ,   0 ],
        [ 5 ,   3 ,   6 ,   7 ,   8 ],
        [ 5 ,   1 ,   3 ,   6 ,   7 ]]

H = len(data)
W = len(data[ 0 ])
v = set()
pq = []
heapq.heappush(pq, ( 0 , ( 0 ,  0 ), []))
while pq:
    l, c, p = heapq.heappop(pq)
    if c == (W -  1 , H -  1 ):
        break
    v.add(c)
    for dy in xrange(- 1 ,  2 ):
        for dx in xrange(- 1 ,  2 ):
            x, y = c[ 0 ] + dx, c[ 1 ] + dy
            if x <  0  or y <  0  or x >= W or y >= H or dx * dy !=  0 :
                continue
            if (x, y) in v:
                continue
            heapq.heappush(pq, (l + data[y][x], (x, y), p + [c]))

p.append(c)
print "Best path: %s" % " -> ".join(map(str, p))

Best path: ( 0 ,  0 ) -> ( 0 ,  1 ) -> ( 0 ,  2 ) -> ( 1 ,  2 ) -> ( 1 ,  3 ) -> ( 2 ,  3 ) -> ( 3 ,  3 ) -> ( 4 ,  3 )

data = [[-x for x in r] for r in data]

Best path: ( 0 ,  0 ) -> ( 0 ,  1 ) -> ( 1 ,  1 ) -> ( 2 ,  1 ) -> ( 3 ,  1 ) -> ( 3 ,  2 ) -> ( 4 ,  2 ) -> ( 4 ,  3 )

data = [[-x for x in r] for r in data]

Best path: ( 0 ,  0 ) -> ( 0 ,  1 ) -> ( 1 ,  1 ) -> ( 2 ,  1 ) -> ( 3 ,  1 ) -> ( 3 ,  2 ) -> ( 4 ,  2 ) -> ( 4 ,  3 )

    di =  1 : dj = - 1 
...
            ni = di: nj = dj
...
        i = i + ni: j = j + nj