Djikstra's algorithm with change in cost function

Question

I am facing the following coding challenge question:

"You are at start location [0, 0] in mountain area of NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). Return minimal number of climb rounds to target location [N-1, N-1]. Number of climb rounds between adjacent locations is defined as difference of location altitudes (ascending or descending). Location altitude is defined as an integer number (0-9)."

So for example, the result of

  "010",
  "010",
  "010"

Will be 2 because we climb in [0,1] from 0 to 1 and in [2,2] we go down from 1 to 0. My idea is to implement the Dijkstra's algorithm, with a change in the cost function. The distance will be given as: distance_current_vertex_to_0 + delta_next_vertex_to_current_vertex However, something is wrong in my implementation because I always get a local optima instead of a global optima. For example

"9589747",
"9141279",
"2915307",
"5271413",
"8795390",
"1251866",
"4697825"

Should return 26, but with my code implementation I get 30. So my question is: what is not correct in my version of Djikstra's algorithm ? I am inspiring myself from this explanation video. The coding question comes from: here.

My code:

from copy import deepcopy
import numpy as np

def search_neighbours(pos, vv, min_distances, nearest_neighbors, m):

    pos_id = int(pos[0] * len(m) + pos[1])
    sorted_neighbours = {}

    #for the current vertex, examine it's unvisited vertices
    for key, comb in enumerate([[1, 0], [0, 1], [0, -1], [-1, 0]]):

        i = comb[0]
        j = comb[1]

        next_pos = [pos[0] + i, pos[1] + j]
        next_pos_id = int(next_pos[0] * len(m) + next_pos[1])

        if 0 <= next_pos[0] < len(m) and 0 <= next_pos[1] < len(m):

            #if the calculated distance of a vertex ist less than the known distance, update the shortest distance
            d = min_distances[pos[0]][pos[1]] + abs(int(m[next_pos[0]][next_pos[1]]) - int(m[pos[0]][pos[1]]))
            if d < min_distances[next_pos[0]][next_pos[1]]:
                min_distances[next_pos[0]][next_pos[1]] = d
                #update the previous vertex for each of the updated distances
                nearest_neighbors[next_pos[0]][next_pos[1]] = pos

            if next_pos_id not in vv:
                sorted_neighbours[tuple(comb)] = abs(int(m[next_pos[0]][next_pos[1]]) - int(m[pos[0]][pos[1]]))

    sorted_neighbours = {k: v for k, v in sorted(sorted_neighbours.items(), key=lambda item: item[1])}
    #add the current vertex to the list of vertices
    vv.append(pos_id)

    #visit the unvisited vertex with the smallest distance from the start vertex
    if pos == [len(m) - 1, len(m) - 1]:
        return True
    else:
        k = 0
        while k < len(sorted_neighbours.keys()):
            dir = list(sorted_neighbours.keys())[k]
            next_pos = [pos[0] + dir[0], pos[1] + dir[1]]
            if not search_neighbours(next_pos, vv, min_distances, nearest_neighbors, m):
                k += 1
            else:
                return True

        return False #in this case ended somewhere else on the map and don't want that

def path_finder(m):
    print(m)
    m = m.split("\n")
    pos = [0, 0]
    vv = []  # visited vertices
    min_distances = [[99 for _ in range(len(m))] for _ in range(len(m))]
    min_distances[0][0] = 0
    nearest_neighbors = [[0 for _ in range(len(m))] for _ in range(len(m))]
    nearest_neighbors[0][0] = [0,0]
    search_neighbours(pos, vv, min_distances, nearest_neighbors, m)
    return min_distances[len(m) - 1][len(m) - 1]

m = "\n".join([
    "9589747",
    "9141279",
    "2915307",
    "5271413",
    "8795390",
    "1251866",
    "4697825"
])


path_finder(m)

Answer 1

Here is what Dijkstra looks like:

def dijkstra(m):
    heights = [[int(c) for c in line] for line in m.split()]
    n, m = len(heights), len(heights[0])
    distances = [[float('inf') for _ in range(m)] for _ in range(n)]
    heap = [((0, 0, 0))]  # cost so far, x, y
    while heap:
        prev_distance, x, y = heapq.heappop(heap)
        if (x, y) == (m-1, n-1):
            return prev_distance
        for stepx, stepy in ((0, 1), (1, 0), (-1, 0), (0, -1)):
            new_x, new_y = x + stepx, y + stepy
            if not 0 <= new_x < m or not 0<= new_y < n:
                continue  # out of bounds, ignore
            new_distance = prev_distance + abs(heights[y][x] - heights[new_y][new_x])
            if new_distance < distances[new_y][new_x]:  # expand
                distances[new_y][new_x] = new_distance
                heapq.heappush(heap, (new_distance, new_x, new_y))
    return -1  # path not found

dijkstra(m) returns 26, as expected