如何检测网格上的方块,这些方块在添加块之后永远不会成为最短路径的一部分？
Blu*_*eft 13 algorithm graph-theory graph path-finding shortest-path
我有一个带有开始,结束和一些墙的网格.单位从开始到结束采用最短路径(仅向上/向下/向左/向右移动),而不穿过墙壁.
允许用户添加他们想要更改路径的额外墙.
但是,请注意,无论添加多少墙壁或添加它们的位置,都有一些方块永远不会成为最短路径的一部分!
这些方块永远不会成为最短路径的一部分!
我正在寻找一种方法来检测哪些方块永远不会成为最短路径的一部分.
以上案例很容易找到; 但还有更复杂的案例.考虑:
在上图中,没有带红点的正方形可以成为最佳路径的一部分,因为该区域只有一个入口,并且它只有两个宽度.如果它是三个宽度的空间,或者如果任何一个墙被移除,那么大多数这些正方形可能是最佳路径的一部分.
我一直试图找出一种方法来检测上述情况(主要是使用最小割和洪水填充),但没有成功.有谁知道解决这个问题的方法？
考虑从 S 到 F 的任何路径。该路径可能是最短路径（如果删除每隔一个方块），除非您可以仅使用这些图块来走“捷径”。仅当路径中存在两个不相邻的相邻方块时，才会发生这种情况。所以你需要考虑所有相邻的方块对；它们与 S 或 F 断开的任何东西（不断开 S 与 F 的连接）都不能成为最短路径的一部分。此外，可以通过单个方块断开的图块不能成为从 S 到 F 的任何路径（不重复顶点）的一部分，因此它们也需要走。
令 N 为网格中的方格数。对于任何特定的一对正方形（有 O(N) 个），可以通过洪水填充在 O(N) 时间内计算出断开的内容，因此这是 O(N^2)。这比你提到的最小切割便宜，所以我认为它对你来说足够便宜。