Feature #8: Optimal Path

Description

Uber is one of the most popular ride-hailing applications. It provides a choice of a variety of vehicles to the passengers that use it for transport. Uber always uses an optimal path to save its passenger’s time. The terrain is represented as a 2D grid. A passenger waits on one end of the grid and a driver is present on another end. This feature will show us how to find the optimal path for the driver to get to the passenger.

Solution

A new path metric is evaluated. The terrain is represented as a 2D grid, and the cost of going from one point to an adjacent one is given as an integer.

Here is how the implementation of this feature will take place:

1. We can think of this problem as a shortest path problem in a 2D rectangular graph, where the values in the input array are edge weights.

2. Since the driver can only travel right or downward, the optimal way to get to any of the cells in the first row is to travel right. Thus, we can iteratively calculate the costs along the first row as $cost[0][i] = cost[0][i] + cost[0][i-1]$ for all $i = 1, 2,$ ...