fork download
copy 
  1. def find_shortest_path(grid, start_node, end_node):
  2.     marked_grid = [[None for i in range(len(j))] for j in grid]
  3.     step = 0
  4.     current_wave = [start_node]
  5.     manhattan_distance = ((-1, 0), (1, 0), (0, -1), (0, 1))
  6.  
  7.     def generate_new_wave(current, new_wave):
  8.         possible_steps = list(filter(lambda x: -1 not in x and len(marked_grid) not in x
  9.                                                            and marked_grid[x[0]][x[1]] is None
  10.                                                            and x not in new_wave,
  11.                                      [tuple(map(lambda x, y: x + y, current, n)) for n in manhattan_distance]))
  12.         for step in possible_steps:
  13.             yield step
  14.  
  15.     def build_new_wave():
  16.         new_wave = []
  17.         for current in current_wave:
  18.             marked_grid[current[0]][current[1]] = step
  19.  
  20.             for drop in generate_new_wave(current, new_wave):
  21.                 new_wave.append(drop)
  22.  
  23.         return new_wave
  24.  
  25.     while marked_grid[end_node[0]][end_node[1]] is None:
  26.         if len(current_wave) == 0:
  27.             step += 1
  28.             return False
  29.  
  30.         current_wave = build_new_wave()
  31.         step += 1
  32.  
  33.     recovered_path = []
  34.     step -= 1
  35.  
  36.     while step != 0:
  37.         recovered_path.append(end_node)
  38.         for n in manhattan_distance:
  39.             candidate = tuple(map(lambda x, y: x + y, end_node, n))
  40.             try:
  41.                 if marked_grid[candidate[0]][candidate[1]] == step - 1:
  42.                     end_node = candidate
  43.                     step -= 1
  44.                     break
  45.             except IndexError:
  46.                 pass
  47.  
  48.     return list(reversed(recovered_path + [start_node]))
  49.  
  50.  
  51. grid = [[(0,0), (0,1), (0,2), (0,3), (0,4)],
  52.         [(1,0), (1,1), (1,2), (1,3), (1,4)],
  53.         [(2,0), (2,1), (2,2), (2,3), (2,4)],
  54.         [(3,0), (3,1), (3,2), (3,3), (3,4)],
  55.         [(4,0), (4,1), (4,2), (4,3), (4,4)]
  56.         ]
  57.  
  58. start_node = (0, 0)
  59. end_node = (4, 4)
  60.  
  61. print(find_shortest_path(grid, start_node, end_node))
Success #stdin #stdout 0.01s 9992KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 4), (2, 4), (3, 4), (4, 4)]
https://ideone.com/mIV0FM
language:
Python 3 (python  3.9.5)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!