[Introduction to Algorithm] Find the shortest path [Python3]

theme

Find a route that connects the start point and the goal point at the lowest cost on a map that has terrain cost as information. (For example, in SRPG games, terrain costs are taken into account when moving to flatlands, houses, forests, and mountains.)

algorithm

1. Prepare an array corresponding to the coordinates and terrain cost (cost_map)
2. Find the cost of moving to each point starting from the goal point and create an array (rout_cost)
3. Based on the movement cost (rout_cost) of each point, follow the point with the lowest cost from the starting point.

Note) Supplement (Technique used when writing a program) Use a recursive function.

Practice

1. For example, consider the shortest path from the start (x3, y0) to the goal (x1, y6) on a map with the following terrain cost.

Prepare an array cost_map with terrain cost as an element and an array rout_cost with an infinite value as an element.

alg_01.py

s = [3,0]; g = [1,6]  ## start and goal position
cost_map = [[4,3,1,1,1,2,3],\
            [3,2,1,2,1,1,1],\
            [2,1,3,3,2,3,2],\
            [2,3,5,3,2,4,3]]
m = len(cost_map)
n = len(cost_map[0])
rout_cost = [[float("inf") for j in range(n)] for i in range(m)]

2. Calculate the movement cost to each point starting from the goal point, and update the rout_cost prepared above based on the calculation result.

alg_02.py

def calc_rout_cost(x,y,cost_tmp):
    cost_tmp += cost_map[x][y]
    if cost_tmp < rout_cost[x][y]:
        rout_cost[x][y] = cost_tmp
        if y < n-1:
            calc_rout_cost(x,y+1,cost_tmp)
        if y > 0:
            calc_rout_cost(x,y-1,cost_tmp)
        if x < m-1:
            calc_rout_cost(x+1,y,cost_tmp)
        if x > 0:
            calc_rout_cost(x-1,y,cost_tmp)
calc_rout_cost(g[0],g[1],-cost_map[g[0]][g[1]])

The completed rout_cost is as follows. Note that the goal point (x6, y1) will be zero.

3. Finally, find the shortest route from the start to the goal.

alg_03.py

def search_rout(x,y):
    tmp = rout_cost[x][y]
    tmp_x, tmp_y = x, y
    if x > 0 and rout_cost[x-1][y] < tmp :
        tmp_x, tmp_y = x-1, y
        tmp = rout_cost[tmp_x][tmp_y]
    if x < m-1 and rout_cost[x+1][y] < tmp :
        tmp_x, tmp_y = x+1, y
        tmp = rout_cost[tmp_x][tmp_y]
    if y > 0 and rout_cost[x][y-1] < tmp :
        tmp_x, tmp_y = x, y-1
        tmp = rout_cost[tmp_x][tmp_y]
    if y < n-1 and rout_cost[x][y+1] < tmp :
        tmp_x, tmp_y = x, y+1
        tmp = rout_cost[tmp_x][tmp_y]
    if rout_cost[x][y] == 0: return;
    rout_list.append([tmp_x,tmp_y])
    search_rout(tmp_x,tmp_y)

rout_list = []
rout_list.append(s)
search_rout(s[0],s[1])

The shortest path is

result.py

print(rout_list)
## [[3, 0], [2, 0], [2, 1], [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6]]

Will be.

References

Masakazu Yanai "Code Puzzle for Programmers" Gijutsu-Hyoronsha (2014) Please refer to the literature for a detailed explanation. It is written in Javascript.