在网格上找到点和行之间的最短路径
Finding the shortest path between a point and a row on a grid
我知道有算法可以找到两点之间的最短路径，例如How to calculate the shortest path between two points in a grid中回答的算法。
但是，现在，我有一个 N * M 网格，其中行从 0 到 N - 1，列从 0 到 M - 1，其中每个网格都包含障碍物（或者你可以认为它是两个网格之间的距离）。比如我下面有一个4*4的格子：
5 7 8 2
2 7 4 3
6 4 3 2
5 7 2 5
我想找到左上角和底行之间的最短距离，即 (0, 0) 和 (X, 3) 之间的距离，其中 X 可以是从 0 开始的任何数字到 3.
我可以找出 (0, 0) -> (0, 3) 到 (0, 0) -> (3, 3) 之间的每条最短路径，但这可能太慢了。这个问题有更有效的算法/方法吗？
这比您想象的要多，有一个很好的方法可以解释这一点。
你可以想象你的网格是一个图表。每个单元格都是一个节点，从每个单元格到每个相邻单元格都有适当成本的边。
考虑在图中添加一个新节点，并通过成本为零的边将最后一行中的所有内容连接到该新节点。现在，考虑找到从左上角到您刚刚添加的魔法新节点的最短路径。那里的最短路径将对应于通过网格的路径，该路径在最后一步离开最后一行并进入这个新节点。由于边到新节点的成本为零，从左上角节点到这个新节点的最便宜路径的成本是从左上角到最后一行中任何单元格的最佳路径的成本.
换句话说，如果你能解决一对节点之间的最短路径问题，你就能解决图中任意节点到任意一个节点的最短路径问题。
你能找到一种方法来适应这种技术，以便你也可以找到第一行中的任何内容和最后一行中的任何内容之间的最短路径吗？
我知道有算法可以找到两点之间的最短路径，例如How to calculate the shortest path between two points in a grid中回答的算法。
但是，现在，我有一个 N * M 网格，其中行从 0 到 N - 1，列从 0 到 M - 1，其中每个网格都包含障碍物（或者你可以认为它是两个网格之间的距离）。比如我下面有一个4*4的格子：
5 7 8 2
2 7 4 3
6 4 3 2
5 7 2 5
我想找到左上角和底行之间的最短距离，即 (0, 0) 和 (X, 3) 之间的距离，其中 X 可以是从 0 开始的任何数字到 3.
我可以找出 (0, 0) -> (0, 3) 到 (0, 0) -> (3, 3) 之间的每条最短路径，但这可能太慢了。这个问题有更有效的算法/方法吗？
这比您想象的要多，有一个很好的方法可以解释这一点。
你可以想象你的网格是一个图表。每个单元格都是一个节点，从每个单元格到每个相邻单元格都有适当成本的边。
考虑在图中添加一个新节点，并通过成本为零的边将最后一行中的所有内容连接到该新节点。现在，考虑找到从左上角到您刚刚添加的魔法新节点的最短路径。那里的最短路径将对应于通过网格的路径，该路径在最后一步离开最后一行并进入这个新节点。由于边到新节点的成本为零，从左上角节点到这个新节点的最便宜路径的成本是从左上角到最后一行中任何单元格的最佳路径的成本.
换句话说，如果你能解决一对节点之间的最短路径问题，你就能解决图中任意节点到任意一个节点的最短路径问题。
你能找到一种方法来适应这种技术，以便你也可以找到第一行中的任何内容和最后一行中的任何内容之间的最短路径吗？