Want algorithm to find shortest path in grid which 3*3 dimension-CodePudding

I need a help on below image I want to achieve below logic in Python and I am newbie in Python.

Any help is appreciated.

CodePudding user response：

We can easily solve this problem by using recursion. The idea is to start from the top-left cell of the matrix and recur for the next node (immediate right or immediate bottom cell) and keep on doing that for every visited cell until the destination is reached. Also maintain a path array to store the nodes in the current path and update the path array (including the current node) whenever any cell is visited. Now, whenever the destination (bottom-right corner) is reached, print the path array.

CodePudding user response：

I would suggest to seek for every possible path. An example from link then to compute every possible sums and look for the smallest

import numpy as np
import copy

def findPaths(mat, path,paths, i, j):
    # base case
    if not mat or not len(mat):
        return
    (M, N) = (len(mat), len(mat[0]))
    # if the last cell is reached, print the route
    if i == M - 1 and j == N - 1:
        paths.append(copy.deepcopy(path   [[i,j]]    ))
        return
    # include the current cell in the path
    path.append( [i,j])
    # move right
    if 0 <= i < M and 0 <= j   1 < N:
        findPaths(mat, path,paths, i, j   1)
    # move down
    if 0 <= i   1 < M and 0 <= j < N:
        findPaths(mat, path,paths, i   1, j)
    # backtrack: remove the current cell from the path
    path.pop()


if __name__ == '__main__':
    mat = [ [2,5,4],
            [3,2,1],
            [8,0,3] ]

    path = []
    paths = []
    x = y = 0
    #find all possible paths
    findPaths(mat, path,paths, x, y)
    print(paths)
    #get the sum of all paths
    All_sums = []
    for path in paths:
        one_sum = 0
        for p in path:
            one_sum  = mat[p[0]][p[1]]
        All_sums.append(one_sum)
    print(All_sums)
    #get lower path
    min_path = np.argmin(All_sums)
    print(min_path)
    #print the path
    print(paths[min_path])
    #print the val sequence
    print([mat[p[0]][p[1]] for p in paths[min_path]])