是否有一个图算法来寻找节点之间的最短路径，合并要避免的节点？
假设我有一个节点表示位置的图。从某些节点N开始，我想经由可能的最短路径到达另一个节点M。问题是我想避免一些节点，与它们保持一定的距离（比如至少有D个节点）。
是否有一种图算法可以解决具有节点回避要求的最短路径问题？加权图（从待避免节点发出无限长边）是这里的解决方案吗？
共有1个答案
暂时消除必须避免的节点及其附近的节点，或将相应边的权重更改为无穷大。然后使用任何标准的路径查找算法。
-
Dijkstra算法说 对于图中给定的源节点，算法找到该节点和其他节点之间的最短路径 我得到了算法来找到那个节点和其他节点之间的最短路径。但是我的问题是，如果我需要为Linkedin/facebook这样的大图找到两个特定节点（比如N1和N2）的最短路径，我需要计算该节点N1和领英上其他节点（用户，意味着十亿用户）之间的距离吗首先，将其存储在高速缓存中，然后在询问两个节点的最短距离时从高速缓存中返
-
我试图通过一个节点图进行广度优先搜索遍历，然后我将尝试找到一个节点和另一个节点之间的最短距离。这就是维基百科的BFS算法： 我有自己的节点类，节点的距离设置为最大。我的版本基于第一个代码的风格： 我试图让这段代码也能找到一个节点和另一个节点之间的最短路径。例如 我如何修改BFS代码来实现这一点？如果在这个循环中是不可能的，那么还有什么其他的方法呢？ 如果我的代码或我的要求有任何混淆，请通知我。非常
-
我有一个有向加权图
-
假设我有一个无向多图，即一个(G，E)对，其中G是一个有限的结点集，E是一个有限的边集。我正在寻找一个算法，将分配一个单一的字符串值到每个节点在以下的约束。 1. 每个节点都被赋予一组约束（可能是空的），这些约束限制了允许的值。我希望至少支持以下类型的值约束： null 有两种类型的边缘： 不同， 相同， 这意味着应该为相关节点分配不同/相同的值（意味着不相等/相等的字符串）。 null 这意味着
-
我正在上面的图上运行广度优先搜索，查找从到的最短路径。 我的代码 我需要追踪BFS ALGO通过的节点。遍历以到达节点6，如。为此，我创建了一个名为的列表&试图存储访问节点的前一个节点，以获得节点列表。转介
-
我正在寻找最有效的算法，根据大O符号，在未加权有向图中找到两个节点之间的最短路径。 我主要分为带堆的Dijkstra和呼吸优先搜索，如果图加权，我通常会使用堆。 在这种情况下，未加权的图是否会使Dijkstra的使用效率低于BFS？