https://leetcode.com/problems/path-with-minimum-effort/
Bellman-Ford算法，Dijkstra算法

个人解法

  1. class Solution:
  2.     def minimumEffortPath(self, h: List[List[int]]) -> int:
  3.         m, n = len(h), len(h[0])
  4.         d = [[math.inf for j in range(n)] for i in range(m)]
  5.         d[0][0] = 0
  7.         q = collections.deque([(0, 0)])
  8.         in_q = set([(0, 0)])
  10.         while q:
  11.             x, y = q.popleft()
  12.             in_q.remove((x, y))
  13.             for xx, yy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
  14.                 if 0 <= xx < m and 0 <= yy < n:
  15.                     l = max(d[x][y], abs(h[x][y] - h[xx][yy]))
  16.                     if l < d[xx][yy]:
  17.                         d[xx][yy] = l
  18.                         if (xx, yy) not in in_q:
  19.                             in_q.add((xx, yy))
  20.                             q.append((xx, yy))
  22.         return d[m - 1][n - 1]

题目分析

题目没什么好说的，还是很容易想到，是图的最短路径的变种。

但是问题在于，课堂上学的最短路径，只是知道思想，实现的时候也是简单的邻接矩阵形式，遇到形式变一变，评估指标变一变，不见得能很快写出来。

Bellman-Ford算法

  1. queue q
  2. while q is not empty:
  3.     v = dequeue(q)
  4.     for each w adjacent v:
  5.         if w.dist > v.dist + cost(v,w):
  6.             w.dist = v.dist + cost(v,w)
  7.             w.path = v
  8.             if w is not in q:
  9.                 enqueue(w, q)

以上形式是加了SPFA优化的，形式十分简洁，但是理解其为什么正确还是有一点不直观，这里也不打算说明，包括该算法如何处理有负边的情况。

这道题用该算法很直观，题解中便是采用这种形式，矩阵中的相邻关系可以直接用上下左右的坐标来确定，而记录是否在q中以避免重复放到q里用额外的set判断是可以的。

Dijkstra算法

Dijkstra算法应当是最短路径算法里用的最普遍的了，正如二分查找在查找中的应用。然而，正如二分查找：

More than 90% of programmers can’t write binary search code correctly.

一样，Dijkstra的灵活运用和实现也是需要下一点功夫的。

之前的Dijkstra往往都只是遍历一遍距离数组，找到最小的距离对应的点，那么如果用最小堆优化呢？在python或者其它语言里有现成的堆的实现，可以轻松优化：

  1. class Solution:
  2.     def minimumEffortPath(self, h: List[List[int]]) -> int:
  3.         m, n = len(h), len(h[0])
  4.         d = [[math.inf for j in range(n)] for i in range(m)]
  5.         d[0][0] = 0
  7.         q = [(0, 0, 0)]
  9.         while q:
  10.             a, x, y = heapq.heappop(q)
  11.             if x == m - 1 and y == n - 1:
  12.                 return a
  13.             for xx, yy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
  14.                 if 0 <= xx < m and 0 <= yy < n:
  15.                     l = max(d[x][y], abs(h[x][y] - h[xx][yy]))
  16.                     if l < d[xx][yy]:
  17.                         d[xx][yy] = l
  18.                         heapq.heappush(q, (d[xx][yy], xx, yy))
  20.         return d[m - 1][n - 1]

其中，#11-12做了一个提早判断，可以提升算法效率

对比两个代码可以看出，Dijkstra就是在Bellman-Ford算法基础上，加了最短距离的贪心判断，提升了一些效率。
(个人理解，似乎关于Bellman-Ford+SPFA和Dijkstra还是有很大区别的）

其它解法

这道题官方提示里给出了DFS/BFS + 二分查找的方式
因为给定一个阈值，可以通过DFS/BFS判断能不能从起点走到终点，那么只要对这个阈值二分查找确定就可以了，实际实现的时候可能还要注意细节方面的内容。
具体可以看：https://leetcode.com/problems/path-with-minimum-effort/discuss/909002/JavaPython-3-3-codes%3A-Binary-Search-Bellman-Ford-and-Dijkstra-w-brief-explanation-and-analysis.