不使用Dijkstra的带特殊权重规则BFS最短路径算法优化求助

核心思路是把路径的两种状态（是否经过顶点k）拆分计算，利用两次普通BFS完成结果推导，完全不需要枚举所有路径，也不需要用到Dijkstra算法。

原理说明 #

路径的成本可以拆分为两种独立场景取最小值：

1. 路径全程没有经过k，此时成本就是普通无权重图从s到v的最短路径长度（每条边成本为1）
2. 路径经过k，此时总成本可以拆分为「s到k的最短路径成本」 + 「k到v的最短路径长度 * 5」（k之后的每条边成本为5，边数越少总成本越低）

两个场景的结果取最小值，就是对应顶点v的最低成本c(s,v)。不需要考虑多次经过k的情况，因为k之后的边权重更高，重复经过k只会额外增加成本，不可能得到更优结果。

具体实现步骤 #

• 第一步：以s为起点对原图做普通BFS，计算所有顶点的最短路径长度d_s，如果顶点不可达记为无穷大。这一步得到的是所有不经过k的路径的最小成本。
• 第二步：以k为起点对原图做普通BFS，计算所有顶点的最短路径长度d_k，不可达同样记为无穷大。
• 第三步：对每个顶点v∈V，计算c(s,v) = min(d_s[v], d_s[k] + 5 * d_k[v])

边界处理 #

• 如果d_s[k]为无穷大（s到k不可达），则所有顶点的c(s,v)直接等于d_s[v]即可，不存在经过k的可行路径。
• 顶点k本身的成本自动匹配为d_s[k]，符合规则要求。

伪代码示例 #

from collections import deque

def min_cost_calculate(V, adj, s, k):
    # 初始化距离数组，inf代表不可达
    d_s = [float('inf')] * len(V)
    d_k = [float('inf')] * len(V)

    # 第一次BFS：从s出发计算最短路径
    q = deque([s])
    d_s[s] = 0
    while q:
        u = q.popleft()
        for v in adj[u]:
            if d_s[v] == float('inf'):
                d_s[v] = d_s[u] + 1
                q.append(v)
    
    # s到k不可达，直接返回d_s作为结果
    if d_s[k] == float('inf'):
        return d_s
    
    # 第二次BFS：从k出发计算最短路径
    q = deque([k])
    d_k[k] = 0
    while q:
        u = q.popleft()
        for v in adj[u]:
            if d_k[v] == float('inf'):
                d_k[v] = d_k[u] + 1
                q.append(v)
    
    # 遍历每个顶点取最小成本
    res = []
    for v in V:
        res.append(min(d_s[v], d_s[k] + 5 * d_k[v]))
    return res

复杂度分析 #

两次BFS的时间复杂度均为O(V+E)，最后遍历顶点的时间复杂度为O(V)，整体时间复杂度为O(V+E)，远优于枚举路径的方案，适合大规模图使用。

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