带负弧的加权图：基于igraph的Bellman-Ford最短路径跳数计算

背景回顾 #

原场景中，图的边权重代表关系重要性，因此最短路径计算时需将权重转换为1/weights（算法默认权重为路径成本）。原实现依赖get_shortest_paths方法，但该方法默认的Dijkstra算法不支持负权弧，当图中存在负权弧时必须调整算法逻辑。

关键调整点 #

• 替换最短路径算法：当图存在负权弧且无负环时，改用Bellman-Ford算法；若存在负环，需先处理负环或跳过受影响的节点对。igraph的get_shortest_paths支持通过algorithm参数指定算法。
• 捕获负环异常：Bellman-Ford算法检测到负环时会抛出异常，需捕获并标记这类无效路径。
• 保留跳数计算逻辑：依然通过提取路径的边数量来得到跳数。

调整后的代码实现 #

import numpy as np
import igraph as ig

def n_hops_with_negative_weights(s, t, weights):
    try:
        # 使用Bellman-Ford算法适配负权弧，存在负环时会抛出异常
        sps = g_GC_u.get_shortest_paths(
            s, t, 
            output='epath', 
            weights=weights,
            algorithm="bellman_ford"
        )
        # 返回每个目标节点对应的路径跳数（边的数量）
        return [len(path) for path in sps]
    except ig.InternalError as e:
        # 捕获负环异常，用-1标记无效路径（可根据需求调整标记值）
        if "negative cycle" in str(e):
            return [-1] * len(t) if isinstance(t, list) else [-1]
        else:
            raise

# 随机选取200个源节点
src = g_GC_u.vs.indices
np.random.shuffle(src)
src = src[:200]
# 目标节点设为所有节点（可按需调整范围）
trg = g_GC_u.vs.indices

n_hops_w = []
for s in src:
    n_hops_w += n_hops_with_negative_weights(s, trg, weights)

补充说明 #

1. 负环处理：若图中存在负环，源节点到负环内或可达负环的节点不存在有效最短路径（成本可无限降低），这里用-1标记，你可根据业务需求改为np.nan或其他值。
2. 算法优化：如果图规模较大，Bellman-Ford时间复杂度较高（O(V*E)），可改用Johnson算法（设置algorithm="johnson"），该算法更适合多源最短路径场景，效率更高。
3. 权重转换注意：确保weights = 1 / np.array(g_GC_u.es["weight"])转换正确，若原权重为0，需额外处理（比如设置极小值避免除以0）。

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