Grid Routing With Dijkstra or A*

MediumPython

Problem

A Dataiku DSS plugin represents a routing surface as a rectangular grid. Each cell contains -1 for an obstacle or a positive traversal cost. Given a start and goal cell, return an optimal route that minimizes the sum of costs for entered cells.

You may move up, down, left, or right. Diagonal movement is not allowed. The start cell contributes zero cost because the route begins there. Return an ordered list of [row, column] coordinates, including both endpoints. If the goal is unreachable, return an empty list.

Implement optimal_route(grid, start, goal) using Dijkstra's algorithm. An A* implementation with an admissible heuristic is an acceptable alternative.

Formal Specification

grid is a non-empty rectangular list of lists of integers.
start and goal are two-element coordinate lists [row, column].
A traversable cell has a cost from 1 through 9; -1 represents an obstacle.
Return a list of coordinate lists describing a minimum-cost route, or [] when no route exists.
If multiple minimum-cost routes exist, return any one of them.

Constraints

1 <= rows, columns <= 500
-1 <= grid[row][column] <= 9
Traversable cells have costs from 1 through 9
start and goal are traversable coordinates
Movement is limited to four orthogonal directions

Function Signature

def optimal_route(grid, start, goal):

Implement optimal_route(grid, start, goal) using Dijkstra's algorithm. An A* implementation with an admissible heuristic is an acceptable alternative.

Formal Specification

grid is a non-empty rectangular list of lists of integers.
start and goal are two-element coordinate lists [row, column].
A traversable cell has a cost from 1 through 9; -1 represents an obstacle.
Return a list of coordinate lists describing a minimum-cost route, or [] when no route exists.
If multiple minimum-cost routes exist, return any one of them.