如何在自定义带权矩阵中使用Scipy的Dijkstra函数？

问题梳理 #

已实现无权图转带权邻接矩阵（边权重为0或1），但不明确scipy.sparse.csgraph.dijkstra的用法，现有代码未运行，需指导正确调用方式。

关键知识点与代码修正 #

1. Scipy Dijkstra函数核心用法 #

• 输入矩阵支持稠密矩阵（你当前用的二维列表）或稀疏矩阵，矩阵中float("inf")表示无直接边，对角线需设为0（节点到自身的距离）。
• 常用关键参数：
  • indices：指定起点的索引，只计算该点到所有节点的最短路径，避免冗余计算。
  • return_predecessors：设为True时，返回前驱节点数组，用于重构最短路径。
• 返回值：若指定indices，返回一维距离数组（起点到各节点的最短距离）；若未指定，返回二维距离矩阵。

2. 原代码的核心问题 #

• node_ids键类型不统一：先以node对象为键，后续又用node.id取值，会导致KeyError。
• 邻接矩阵未初始化对角线为0：节点到自身的距离应为0，而非inf。
• dijkstra_algorithm函数未处理返回值，也未传入必要参数（如起点indices），无法获取结果。

3. 修改后的完整代码 #

import scipy.sparse.csgraph

def dijkstra_algorithm(matrix, s_id, t_id):
    # 调用dijkstra，指定起点，返回距离和前驱节点
    distances, predecessors = scipy.sparse.csgraph.dijkstra(
        matrix,
        indices=s_id,
        return_predecessors=True,
        directed=True  # 若你的图是有向图，需设为True；无向图设为False
    )
    
    # 获取起点到终点的最短距离
    shortest_distance = distances[t_id]
    
    # 重构最短路径（从终点回溯到起点）
    path = []
    current = t_id
    while current != s_id:
        path.append(current)
        current = predecessors[current]
        # 若出现-1，说明无路径
        if current == -1:
            print("无有效路径")
            return None, None
    path.append(s_id)
    # 反转路径，得到从起点到终点的顺序
    path.reverse()
    
    return shortest_distance, path

def read_special_graph(nodes, s, t):
    # 统一用node.id作为node_ids的键，避免类型不匹配
    node_ids = {node.id: idx for idx, node in enumerate(nodes)}
    
    node_count = len(nodes)
    # 初始化邻接矩阵，对角线设为0，其余为inf
    matrix = [[float("inf")] * node_count for _ in range(node_count)]
    for i in range(node_count):
        matrix[i][i] = 0
    
    s_id = node_ids[s.id]
    t_id = node_ids[t.id]
    
    # 填充邻接矩阵的边权重
    for node in nodes:
        node_id = node_ids[node.id]
        for out_node in node.out_edges:
            out_id = node_ids[out_node.id]
            # 根据节点red属性设置权重
            matrix[node_id][out_id] = 1 if out_node.red else 0
    
    # 调用dijkstra算法并获取结果
    distance, path = dijkstra_algorithm(matrix, s_id, t_id)
    print(f"起点到终点的最短距离: {distance}")
    print(f"最短路径节点索引: {path}")
    return distance, path

注意事项 #

• 若你的图是无向图，需在调用dijkstra时将directed参数设为False，函数会自动处理双向边。
• 若predecessors中出现-1，说明起点到终点无可达路径，需在代码中做相应判断。

内容的提问来源于stack exchange，提问作者nic.o