我知道有一些算法可以找到 two points 之间的最短路径，例如，在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) 之间的每条最短路径，但这可能太慢了 . 这个问题是否有更有效的算法/方法？
1 回答
这比你想象的更多，并且有一个很好的方法可以解释这一点 .
您可以想象您的网格是图形 . 每个单元都是一个节点，每个单元到每个相邻单元的边缘都有适当的成本 .
考虑在图中添加一个新节点，并将最后一行中的所有内容连接到该新节点的成本为零的边缘 . 现在，考虑找到从左上角到刚刚添加的魔术新节点的最短路径 . 那里的最短路径将对应于通过网格的路径，在最后一步，该路径离开最后一行并进入该新节点 . 由于边缘到新节点的成本为零，从左上角节点到这个新节点的最便宜路径的成本是从左上角到最后一行中任何单元的最佳路径的成本 .
换句话说，如果您可以解决一对节点之间的最短路径问题，则可以解决从任何节点到图中许多节点中任何一个节点的最短路径问题 .
你能看到一种方法来适应这种技术，这样你也可以找到第一行中任何东西和最后一行中任何东西之间的最短路径吗？