矩阵中从左上角到右下角最短路径（五种方法）_矩阵从左上角到右下角的最短路径

  题目：给定一个n*m的矩阵，矩阵中元素非负，从左上角到右下角找一条路径，使得路径上元素之和最小，每次只能向右或者向下走一个方格。如下图所示：最短路径是图中绿色部分的元素。

  方法一(转换为图中的最短路径)：我们可以把矩阵中的每个方格当做图中的一个顶点，相邻的方格之间有一条边，每个方格最多有两条出边，(当前方格到右侧方格有一条出边，当前方格到下侧方格有一条出边)。我们把矩阵中的最短路径转换为图中的最短路径，使用Dijstra算法来做此题，我们再次使用最简单的Dijstra算法，没有进行优化。图中总共有n*m个点，因为每一次都需要找到一个最小值，找最小值得代价为o(n*m)，总共需要找o(n*m)个最小值，所以时间复杂度为o(n*n*m*m)。
struct Node
{
	int val;
	int row;
	int col;
	Node(){}
	Node(int v, int r, int c) :val(v), row(r), col(c)
	{}
	friend bool operator<(const Node &lhs, const Node &rhs);
};
 
bool operator<(const Node &lhs, const Node &rhs)
{
	return lhs.val > rhs.val;
}
 
struct Vertex
{
	int dis;
	bool visited;
	Vertex(){}
	Vertex(int d, bool v) :dis(d), visited(v){}
};
 
class Solution {
public:
    Node findMinVal(vector<vector<Vertex>> ve)
    {
    	Node res = Node(INT_MAX, 0, 0);
    	for (int i =