Ever heard about Dijkstra's shallowest path algorithm? Me neither. But I can imagine what it would be.

You're hiking in the wilderness of Northern Canada and you must cross a large river. You have a map of one of the safer places to cross the river showing the depths of the water on a rectangular grid. When crossing the river you can only move from a cell to one of the (up to 8) neighboring cells. You can start anywhere along the left river bank, but you have to stay on the map.

An example of the depths provided on the map is 

```
[[2, 3, 2],
 [1, 1, 4],
 [9, 5, 2],
 [1, 4, 4],
 [1, 5, 4],
 [2, 1, 4],
 [5, 1, 2],
 [5, 5, 5],
 [8, 1, 9]]
```
If you study these numbers, you'll see that there is a path accross the river (from left to right) where the depth never exceeds 2. This path can be described by the list of pairs `[(1, 0), (1, 1), (2, 2)]`. There are also other paths of equal maximum depth, e.g., `[(1, 0), (1, 1), (0, 2)]`. The pairs denote the cells on the path where the first element in each pair is the row and the second element is the column of a cell on the path.

Your job is to write a function `shallowest_path(river)` that takes a list of lists of positive ints (or array of arrays, depending on language) showing the depths of the river as shown in the example above and returns a shallowest path (i.e., the maximum depth is minimal) as a list of coordinate pairs (represented as tuples, Pairs, or arrays, depending on language) as described above. If there are several paths that are equally shallow, the function shall return a shortest such path. All depths are given as positive integers.

Source: codewars | Difficulty: MEDIUM
Tags: Graph algorithms

Starter code: def shallowest_path(river):
	

Solutions:
from heapq import *
MOVES = tuple(((dx, dy) for dx in range(-1, 2) for dy in range(-1, 2) if dx or dy))

def shallowest_path(river):
	(lX, lY) = (len(river), len(river[0]))
	pathDct = {}
	cost = [[(float('inf'), float('inf'))] * lY for _ in range(lX)]
	for x in range(lX):
		cost[x][0] = (river[x][0], 1)
	q = [(river[x][0], lY == 1, 1, (x, 0)) for x in range(lX)]
	heapify(q)
	while not q[0][1]:
		(c, _, steps, pos) = heappop(q)
		(x, y) = pos
		for (dx, dy) in MOVES:
			(a, b) = new = (x + dx, y + dy)
			if 0 <= a < lX and 0 <= b < lY:
				check = (nC, nS) = (max(c, river[a][b]), steps + 1)
				if cost[a][b] > check:
					cost[a][b] = check
					pathDct[new] = pos
					heappush(q, (nC, b == lY - 1, nS, new))
	(path, pos) = ([], q[0][-1])
	while pos:
		path.append(pos)
		pos = pathDct.get(pos)
	return path[::-1]


from heapq import *
from collections import defaultdict
MOVES = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))

def shallowest_path(river):
	q = [(river[x][0], 0, (x, 0)) for x in range(len(river))]
	path = {}
	stored_steps = defaultdict(lambda : float('inf'))
	heapify(q)
	while q:
		(cost, step, (x, y)) = heappop(q)
		if (x, y) == (x, len(river[0]) - 1):
			end = (x, y)
			break
		for (dx, dy) in MOVES:
			xx = dx + x
			yy = dy + y
			if 0 <= xx < len(river) and 0 <= yy < len(river[0]):
				new_step = step + 1
				if new_step < stored_steps[xx, yy]:
					stored_steps[xx, yy] = new_step
					new_cost = max(cost, river[xx][yy])
					path[xx, yy] = (x, y)
					heappush(q, (new_cost, new_step, (xx, yy)))
	coords = [end]
	while coords[-1][1] != 0:
		coords.append(path[end])
		end = path[end]
	return coords[::-1]


def shallowest_path(river):
	depth = {(r, c): d for (r, row) in enumerate(river) for (c, d) in enumerate(row)}
	width = max((c for (_, c) in depth))
	for mx in sorted(set(depth.values())):
		D = {d for d in depth if depth[d] <= mx}
		(paths, D) = ([[d] for d in D if d[1] == 0], {d for d in D if d[1]})
		while paths:
			newp = []
			for p in paths:
				if p[-1][1] == width:
					return p
				for d in {(p[-1][0] + rr, p[-1][1] + cc) for rr in [-1, 0, 1] for cc in [-1, 0, 1]} & D:
					(newp, _) = (newp + [p + [d]], D.discard(d))
			paths = newp


def shallowest_path(river):
	(mx, my, crit) = (len(river[0]), len(river), lambda e: e[0] + len(e[1]))
	M = [[(r[0] * mx * my, [(i, 0)])] + [(99999 * mx * my, [])] * (mx - 1) for (i, r) in enumerate(river)]
	Q = set((((j, 1), (i, 0)) for i in range(my) for j in [i - 1, i, i + 1] if 0 <= j < my and mx > 1))
	while Q:
		(Q, R) = (set(), Q)
		for ((u, v), (i, j)) in R:
			if crit(M[u][v]) > max(M[i][j][0], river[u][v] * mx * my) + len(M[i][j][1]) + 1:
				M[u][v] = (max(M[i][j][0], river[u][v] * mx * my), M[i][j][1] + [(u, v)])
				Q.update((((a, b), (u, v)) for a in [u - 1, u, u + 1] for b in [v, v - 1, v + 1][a == u:] if 0 < b < mx and 0 <= a < my))
	return min(M, key=lambda e: crit(e[-1]))[-1][1]


from collections import namedtuple
import heapq

def shallowest_path(river):
	rows = len(river)
	if rows == 0:
		return []
	cols = len(river[0])
	if cols == 0:
		return []
	Solution = namedtuple('Solution', ['depth', 'path'])
	State = namedtuple('State', ['depth', 'path_length', 'path'])
	best_solution = None
	left_bank_q = [(river[row][0], row, 0) for row in range(rows)]
	heapq.heapify(left_bank_q)
	while left_bank_q:
		visited = set()
		(initial_depth, row, col) = heapq.heappop(left_bank_q)
		walk_q = [State(depth=initial_depth, path_length=1, path=[(row, col)])]
		while walk_q:
			(depth, path_length, path) = heapq.heappop(walk_q)
			(current_row, current_col) = path[-1]
			if (current_row, current_col) in visited or (current_col == 0 and path_length > 1):
				continue
			if current_col == cols - 1:
				if depth == 1 and len(path) == cols:
					return path
				if best_solution is None or depth < best_solution.depth or (depth == best_solution.depth and len(path) < len(best_solution.path)):
					best_solution = Solution(depth, path)
				continue
			visited.add((current_row, current_col))
			best_depth = float('inf') if best_solution is None else best_solution.depth
			for (row, col) in neighbours(river, current_row, current_col):
				if (row, col) not in visited and river[row][col] <= best_depth:
					heapq.heappush(walk_q, State(depth=max(depth, river[row][col]), path_length=path_length + 1, path=path + [(row, col)]))
	return best_solution.path

def neighbours(river, row, col):
	rows = len(river)
	cols = len(river[0])
	return ((row + drow, col + dcol) for drow in [-1, 0, 1] for dcol in [-1, 0, 1] if drow != 0 or dcol != 0 if 0 <= row + drow < rows if 0 <= col + dcol < cols)


from itertools import product
from collections import defaultdict
from heapq import *

def dijkstra(edges, f, t):
	g = defaultdict(list)
	for (l, r, c) in edges:
		g[l].append((c, r))
	(q, seen, mins) = ([(0, f, ())], set(), {f: 0})
	while q:
		(cost, v1, path) = heappop(q)
		if v1 not in seen:
			seen.add(v1)
			path = (v1, path)
			if v1 == t:
				return (cost, path)
			for (c, v2) in g.get(v1, ()):
				if v2 in seen:
					continue
				prev = mins.get(v2, None)
				next = cost + c
				if prev is None or next < prev:
					mins[v2] = next
					heappush(q, (next, v2, path))
	return (float('inf'), ())

def shallowest_path(river):
	d = {(y, x): v for (y, line) in enumerate(river) for (x, v) in enumerate(line)}
	width = len(river[0])
	height = len(river)
	depthmin = max([min((d[y, x] for y in range(height))) for x in range(width)])
	depths = sorted(set([v for v in list(d.values()) if v >= depthmin]))
	start = (0, -1)
	end = (0, width)
	for depth in depths:
		edges = [(start, (y, 0), 0) for y in range(height) if d[y, 0] <= depth]
		edges += [((y, width - 1), end, 0) for y in range(height) if d[y, width - 1] <= depth]
		for k in product(list(range(height)), list(range(width))):
			if not k in d or d[k] > depth:
				continue
			(y, x) = k
			for k1 in [(y - 1, x - 1), (y - 1, x), (y - 1, x + 1), (y, x - 1), (y, x + 1), (y + 1, x - 1), (y + 1, x), (y + 1, x + 1)]:
				if not k1 in d or d[k1] > depth:
					continue
				edges.append((k, k1, 1))
		(dist, res0) = dijkstra(edges, start, end)
		if dist == float('inf'):
			continue
		res = []
		while res0:
			(p, res0) = res0
			res.insert(0, p)
		return res[1:-1]
	return []


from heapq import heappush, heappop

def shallowest_path(river):
	(ls_o_res, hippo, dc) = ({}, [], {(i, 0): {} for i in range(len(river))})
	if len(river[0]) > 1:
		for i in range(len(river)):
			dc[i, 0][i, 0] = ((river[i][0], len([river[i][0]])), (i, 0), [(i, 0)], [river[i][0]])
			heappush(hippo, ((river[i][0], len([river[i][0]])), (i, 0), [(i, 0)], [river[i][0]]))
	else:
		for i in range(len(river)):
			ls_o_res[river[i][0]] = [(i, 0)]
		return ls_o_res[min(ls_o_res.keys())]
	(yb, xb) = (len(river), len(river[0]))
	mito = (float('inf'), float('inf'))
	while hippo:
		vara = heappop(hippo)
		(moves, parent) = ([(1, 0), (-1, 0), (0, 1), (1, 1), (-1, 1), (-1, -1), (1, -1), (0, -1)], vara[1])
		for (y, x) in moves:
			(i, j) = parent
			(i, j) = (i + y, j + x)
			if 0 <= i < yb and 0 <= j < xb:
				path = vara[2] + [(i, j)]
				pathowar = vara[3] + [river[i][j]]
				dist = (max(pathowar), len(pathowar))
				if (i, j) not in dc[i, 0]:
					dc[i, 0][i, j] = (dist, (i, j), path, pathowar)
					heappush(hippo, (dist, (i, j), path, pathowar))
				elif (i, j) in dc[i, 0] and dist < dc[i, 0][i, j][0]:
					dc[i, 0][i, j] = (dist, (i, j), path, pathowar)
					heappush(hippo, (dist, (i, j), path, pathowar))
				if j == xb - 1:
					print(dist)
					if dist < mito:
						mito = dist
						ls_o_res[mito] = path
	return ls_o_res[min(ls_o_res.keys())]


import math

def shallowest_path(river):
	maxsize = 999999999
	steps = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
	(h, w) = (len(river), len(river[0]))
	res = [[]] * h
	for r in range(h):
		res[r] = [(maxsize, [(r, 0)])] * w
	points = []
	for r in range(h):
		res[r][0] = (river[r][0], [(r, 0)])
		points.append((r, 0))
	while len(points) > 0:
		p = points.pop(0)
		(r, c) = (p[0], p[1])
		deep = res[r][c][0]
		path = res[r][c][1]
		length = len(path)
		if c < w - 1:
			for s in steps:
				nr = r + s[0]
				nc = c + s[1]
				if nr >= 0 and nr < h and (nc >= 0) and (nc < w) and ((nr, nc) not in path):
					tdeep = res[nr][nc][0]
					tpath = res[nr][nc][1]
					tlength = len(tpath)
					ndeep = max(deep, river[nr][nc])
					if tdeep > ndeep or (tdeep == ndeep and tlength > length + 1):
						npath = path.copy()
						npath.append((nr, nc))
						res[nr][nc] = (ndeep, npath)
						if (nr, nc) not in points:
							points.append((nr, nc))
	(min_deep, min_path) = (maxsize, [])
	for r in range(h):
		p = res[r][-1]
		if p[0] < min_deep:
			(min_deep, min_path) = (p[0], p[1])
		elif p[0] == min_deep and len(p[1]) < len(min_path):
			(min_deep, min_path) = (p[0], p[1])
	return min_path


import heapq

def get_path(river):
	big_num = 10992312321
	nodes = []
	b = {}
	for y in range(len(river)):
		heapq.heappush(nodes, [river[y][0] * big_num, (y, 0)])
	while nodes[0][1][1] != len(river[0]) - 1:
		(weight, node) = heappop(nodes)
		(ly, lx) = node
		for (dy, dx) in [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]:
			if 0 <= ly + dy < len(river) and 0 <= lx + dx < len(river[0]) and ((ly + dy, lx + dx) not in b):
				b[ly + dy, lx + dx] = (ly, lx)
				new_weight = max([weight // big_num, river[ly + dy][lx + dx]]) * big_num + weight % big_num + 1
				heapq.heappush(nodes, [new_weight, (ly + dy, lx + dx)])
	path = [nodes[0][1]]
	while path[-1][1] != 0:
		path.append(b[path[-1]])
	return (nodes[0][0] // big_num, path)

def shallowest_path(river):
	(cost, path) = get_path(river)
	for y in range(len(river)):
		for x in range(len(river[0])):
			if river[y][x] < cost:
				river[y][x] = 0
	(cost, path) = get_path(river)
	return path[::-1]