如何查找单源点到其余所有顶点且不经过指定顶点集的最短路径

核心逻辑 #

最短路径增加「不经过指定顶点集合」的约束，本质是在路径搜索过程中屏蔽所有属于禁止集合的顶点，不允许这些顶点出现在路径的任何位置。

实现方案（两种可选，按你的使用场景选择） #

方案1：生成过滤子图后计算（通用所有图计算库，兼容性最高） #

• 第一步：校验源点s是否属于禁止顶点集合N，如果是直接返回空结果，不存在有效路径
• 第二步：从原图G中移除所有N包含的顶点，生成仅包含合法顶点的子图G_filtered
• 第三步：在G_filtered上直接调用你原本使用的get_shortest_paths()方法，传入源点在子图中的对应索引，得到的所有路径天然满足不经过N中顶点的约束
• 第四步：如果需要映射回原图顶点ID，提前给顶点加上唯一标识属性，遍历路径做索引转换即可

示例代码（igraph为例）

import igraph as ig

# 替换为你的实际图、源点、禁止顶点集合
G = ig.Graph.Famous("Zachary")
s = 0
N = {2, 5, 7}

if s in N:
    print("源点属于禁止集合，无有效路径")
else:
    # 生成过滤子图，保留所有不在N中的顶点
    keep_ids = [v.index for v in G.vs if v.index not in N]
    G_filtered = G.subgraph(keep_ids)
    # 映射源点到子图索引
    s_sub_idx = G_filtered.vs.find(id=s).index
    # 计算最短路径
    sub_paths = G_filtered.get_shortest_paths(s_sub_idx)
    # 转换为原图索引的路径
    original_paths = [ [G_filtered.vs[i]["id"] for i in path] for path in sub_paths ]

方案2：直接修改搜索逻辑（无需改图结构，适合自定义算法场景） #

如果你是手动实现BFS（无权图）或Dijkstra（有权图）最短路径算法，只需要在顶点扩展步骤增加过滤条件：

• 每次从队列/优先队列取出待扩展的顶点时，先判断该顶点是否属于N
• 如果属于N直接跳过该顶点，不遍历它的邻接边，就可以保证所有生成的路径不会经过禁止顶点

注意事项 #

• 如果禁止集合包含某个目标顶点，对应目标的最短路径会自动返回空，无需额外判断
• 过滤顶点的操作不会增加原有最短路径算法的时间复杂度，仅增加O(n)的集合查询开销
• 使用子图方案时注意原图和子图的顶点索引映射，避免出现索引错位的问题

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