是否有一种图算法可以找到节点之间的最短路径，并结合要避免的节点？

Question

假设我有一个图表，其中包含代表位置的节点。从某个节点 N 开始，我想通过可能的最短路径到达另一个节点 M。要注意的是，有些节点我想避免，与它们保持一定距离（比如至少远离 D 个节点）。

有没有一种图算法可以解决具有节点回避要求的最短路径问题？加权图（具有从要避免的节点发出的无限长度边）是这里的解决方案吗？

Answer 1

暂时消除您必须避开的节点和靠近它们的节点，或者将适当边的权重更改为无穷大。然后使用任何标准路径查找算法。