Grid Routing With Dijkstra or A*

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.