单源最短路径：

路径要有权值，且负权值会失效
一句话概括：按照长度递增的次序产生最短路劲。即：每次对所有可见路径进行排序后，选出最短路径，最后到达终点即为最短路径。
如果权值退化为1，即为广度优先搜索。
**

证明

图G的顶点为集合V
已经过路径集合S

设下一条最短路径（终点为x），那么它只能是弧（v，x）或者通过S中的顶点到达x即（v，vi,….,x）。我们来证明一下：
假设（v，…,x）路径上有一个顶点不在S中，则说明存在一条终点不在S中而长度比此路径还短的路径。但这是不可能的。因为我们按长度递增的顺序来产生各最短路径，所以长度比此路径还短的所有路径均已产生，他们的终点一定在S中。

实现

这里贴一下leetcode 1631 最小体力消耗路劲的解法
因为用到优先队列，所以用python解

  1. class Solution:
  2.     def minimumEffortPath(self, heights: List[List[int]]) -> int:
  3.         m, n = len(heights), len(heights[0])
  4.         q = [(0, 0, 0)]
  5.         dist = [0] + [float("inf")] * (m * n - 1)
  6.         seen = set()
  8.         while q:
  9.             d, x, y = heapq.heappop(q)
  10.             iden = x * n + y
  11.             if iden in seen:
  12.                 continue
  13.             if (x, y) == (m - 1, n - 1):
  14.                 break
  16.             seen.add(iden)
  17.             for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
  18.                 if 0 <= nx < m and 0 <= ny < n and max(d, abs(heights[x][y] - heights[nx][ny])) <= dist[nx * n + ny]:
  19.                     dist[nx * n + ny] = max(d, abs(heights[x][y] - heights[nx][ny]))
  20.                     heapq.heappush(q, (dist[nx * n + ny], nx, ny))
  22.         return dist[m * n - 1]