网格在线阻塞单元格后的最短路径求解：是否存在更优方案？

结论 #

不存在最坏情况时间复杂度优于每次重新计算的解决方案，但存在一些平均场景下更高效的启发式策略。

平均场景的启发式优化思路 #

如果只追求多数场景下的效率，可以尝试以下方法：

• 维护当前已知的所有最短路径集合，每次阻塞单元格时先做检查：
  • 若被阻塞的单元格不在任何一条当前最短路径上，直接输出之前的最短路径长度，无需重新计算；
  • 若该单元格在最短路径上，再触发全量计算。
• 还可以维护从起点A出发的距离数组、从终点B出发的距离数组，当阻塞单元格(u,v)时，仅尝试更新那些依赖(u,v)的节点距离，但这种方法在极端场景下依然无法避免全量计算。

最坏情况无法优化的证明 #

我们可以构造极端场景，让每次阻塞操作完全 invalidate 之前的所有路径信息，必须重新计算：

1. 构造网格：起点A在(0,0)，终点B在(N-1,N-1)，初始最短路径为沿边缘的「右→右→…→下→下→…」路径，长度为2N-2。
2. 每次查询精准阻塞当前最短路径上的未阻塞节点：比如第一次阻塞(1,0)，此时最短路径必须绕路到(0,1)→(1,1)→…→(N-1,N-1)，长度变为2N-1；第二次阻塞(0,1)，路径又要换另一条绕道路线，长度继续增加。
3. 在这种场景下，每次阻塞都会让之前的所有距离信息（比如A到各节点的最短距离）完全失效——原最短路径被切断后，新路径需要遍历大量未被影响的区域，没有任何之前的计算结果可以复用。
4. 从时间复杂度下界看，最坏情况下每次查询都需要遍历O(N²)个节点才能确定新的最短路径，这和重新跑一次BFS/DFS的复杂度完全相同，因此不存在更优的最坏情况算法。

简言之，直觉里的「复用之前信息」只适用于部分场景，但无法覆盖所有极端情况，所以不存在通用的、最坏表现优于重新计算的方案。

内容的提问来源于stack exchange，提问作者mark