如何使用scipy.sparse计算稀疏矩阵中最短路径的权重总和

原有代码问题 #

• 调用shortest_path时未指定unweighted=True，默认按邻接矩阵存储的边权重计算最短路径，与「按边数量判定最短」的需求不符
• 路径长度计算函数边界逻辑错误，源节点到自身的跳数应为0，函数返回值为1
• 直接对默认返回的权重最短距离做除法计算权重的逻辑完全错误，无法得到跳数最短路径的总权重

修正后实现 #

要实现「先按边数求最短路径，再计算该路径总权重」的需求，首先通过无权重BFS得到跳数最短的路径前驱，再回溯路径累加边权重即可，完整实现如下：

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path

# 构造稀疏邻接矩阵，graph[i,j]存储节点i到j的边权重
graph = csr_matrix(graph)
source_idx = 0 # 源节点索引

# 调用shortest_path时指定unweighted=True，按跳数（边数）计算最短路径
# 此时返回的hop_count为各节点到源节点的最短跳数，predecessors为对应路径的前驱节点
hop_count, predecessors = shortest_path(
    csgraph=graph,
    directed=False,
    indices=source_idx,
    return_predecessors=True,
    unweighted=True
)

path_total_weights = []
node_count = graph.shape[0]

for target_idx in range(node_count):
    # 源节点到自身路径权重为0
    if target_idx == source_idx:
        path_total_weights.append(0)
        continue
    # 不可达节点权重标记为无穷大
    if predecessors[target_idx] == -9999:
        path_total_weights.append(float('inf'))
        continue
    # 回溯路径累加边权重
    current = target_idx
    total_w = 0
    while current != source_idx:
        prev_node = predecessors[current]
        total_w += graph[prev_node, current]
        current = prev_node
    path_total_weights.append(total_w)

补充说明 #

• 各节点对应的最短跳数可直接从hop_count数组中获取，无需额外计算
• 若存在多条跳数相同的最短路径，scipy默认返回任意一条路径的前驱，如需统计所有最短路径的权重情况，需自行扩展BFS逻辑记录所有前驱节点

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