题目大意：给定一个m * n的矩阵，每个点都有对应意义的权值，求从起点到终点的最短距离（权值路径）。
以2290题为例，给定m * n的矩阵grid，每个单元格可能有两个值：0表示无障碍物，1表示有障碍物，可以上下左右移动，求从（0,0）到（m – 1, n – 1）需要移除障碍物的最小数目。
我们可以把矩阵中的每个点看作图结构中的某个结点，从该结点到相邻结点需要移除障碍物的个数为边的权值，这样求出从起点到终点的最短路即为所求答案。
解法一：Dijkstra算法
根据Dijkstra的思想，①每次从未标记的结点中选取距离出发点最近的结点，标记并加入最优集合中，②计算刚加入的点A到其相邻结点B的距离，如果dis[A] + grid[A —B] < dis[B]，则更新dis[B]。
上述算法的时间复杂度为O(V^2 + E)，V代表结点集大小，即m * n，E代表边集大小，可用优先队列进行优化：
使用优先队列存储结点以及起点到该结点的最短路长度，即可每次从结点中选取出离出发点最近的结点，若该结点被标记过，删除该结点并重新选取。此时复杂度为O((V + E) * logV)。
Java代码如下：
解法二：0-1 BFS
BFS也能解决上述的最短路问题，即从起点逐层遍历，直到遍历到最终结点。但BFS成功的前提是，所有边的权值均为1，然而当前出现了边的权值为0的情况，此时需要对算法进行修改，使得保证每次遍历时，当前结点到起点的距离大于等于上一次遍历的结点到起点的距离，即保证BFS逐层扩散的正确性。
修改方法：使用双端队列。如果当前结点到某相邻结点的距离为0，则加入队首，否则加入队尾。这样就保证了每次选取的结点必定为当前距离起点最近的结点，因为每次都是从队首取的。
Golang代码：
Original: https://www.cnblogs.com/ThXin/p/16339150.html
Author: 夜满星河
Title: 矩阵中的最短路问题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/608651/
转载文章受原作者版权保护。转载请注明原作者出处！