矩阵中的单对最短路径
Single pair shortest path in a matrix
设一个 MxN 矩阵，其中起始位置为 (0,0)，结束位置为 (M-1,N-1)
.每个方格都有一个正整数，它是在这个方格上移动的成本。对于从开始到结束的最短路径，我应该使用什么算法？我们可以使用图表重现问题。其中正方形是顶点，成本是加权边。
示例
使用 Dijkstra. As soon as you hear "shortest path", look at Dijkstra. In particular, if you search for "dijkstra adjacency matrix" on stack overflow，您将得到十几个问题，讨论如何在表示为矩阵的图形上应用 Dijkstra 的各个方面。您可以通过按如下方式循环输入来从输入矩阵构建邻接矩阵：
create a (rows * cols) * (rows * cols) adjacency matrix
for each square at position row,col in the input matrix
let v = row*cols + col
for all neighboring positions u (at row,col+1; row+1,col; and so on)
set the cost of going from v to u to input[row][col]
您甚至可以跳过邻接矩阵的构建，直接计算邻居和到邻居的距离。这可以节省相当多的内存，但代价是额外的运行时间。
您还可以通过将图形表示为邻接表来节省一些 space，但实现起来稍微复杂一些，而且您似乎才刚刚起步。
设一个 MxN 矩阵，其中起始位置为 (0,0)，结束位置为 (M-1,N-1) .每个方格都有一个正整数，它是在这个方格上移动的成本。对于从开始到结束的最短路径，我应该使用什么算法？我们可以使用图表重现问题。其中正方形是顶点，成本是加权边。
示例
使用 Dijkstra. As soon as you hear "shortest path", look at Dijkstra. In particular, if you search for "dijkstra adjacency matrix" on stack overflow，您将得到十几个问题，讨论如何在表示为矩阵的图形上应用 Dijkstra 的各个方面。您可以通过按如下方式循环输入来从输入矩阵构建邻接矩阵：
create a (rows * cols) * (rows * cols) adjacency matrix
for each square at position row,col in the input matrix
let v = row*cols + col
for all neighboring positions u (at row,col+1; row+1,col; and so on)
set the cost of going from v to u to input[row][col]
您甚至可以跳过邻接矩阵的构建，直接计算邻居和到邻居的距离。这可以节省相当多的内存，但代价是额外的运行时间。
您还可以通过将图形表示为邻接表来节省一些 space，但实现起来稍微复杂一些，而且您似乎才刚刚起步。