如何在pandas存储的CSV格式带权有向2D图中获取A到B的最短路径节点序列

核心原理 #

要获取完整的路径节点序列，只需要在标准Dijkstra算法的基础上额外维护一个前驱节点映射表，记录每个节点的最短路径是从哪个前序节点跳转过来的。算法执行完成后从终点反向遍历前驱映射表直到起点，再反转序列即可得到正向的最短路径。

实现步骤 #

1. 邻接矩阵数据预处理 #

首先读取CSV格式的邻接矩阵，统一处理无穷值，转成算法可直接调用的结构：

import pandas as pd
import numpy as np
import heapq

# 读取CSV，第一列是行索引（节点ID）
df = pd.read_csv("weight_graph.csv", index_col=0)
# 确保索引和列名都是整数类型（节点ID为数值的场景）
df.index = df.index.astype(int)
df.columns = df.columns.astype(int)
# 统一无穷值为np.inf
df = df.replace([np.inf, 'inf', float('inf')], np.inf)

2. 带前驱记录的Dijkstra算法实现 #

def shortestRoute(start, end, adj_df):
    # 初始化距离字典：所有节点初始距离为无穷大
    dist = {node: np.inf for node in adj_df.index}
    dist[start] = 0
    # 核心：前驱节点字典，记录每个节点最短路径的上一个节点
    prev = {node: None for node in adj_df.index}
    # 优先队列，存储(当前距离, 节点ID)
    heap = []
    heapq.heappush(heap, (0, start))
    visited = set()

    while heap:
        current_dist, current_node = heapq.heappop(heap)
        if current_node in visited:
            continue
        if current_node == end:
            break
        visited.add(current_node)
        # 遍历所有邻居节点
        for neighbor in adj_df.columns:
            weight = adj_df.loc[current_node, neighbor]
            if weight == np.inf:
                continue
            # 计算通过当前节点到邻居的新距离
            new_dist = current_dist + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                prev[neighbor] = current_node
                heapq.heappush(heap, (new_dist, neighbor))
    
    # 回溯生成路径
    if dist[end] == np.inf:
        return "无可用路径"
    # 从终点反向找前驱
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = prev[current]
    # 反转得到正向路径
    path = path[::-1]
    # 拼接成要求的输出格式
    return " -> ".join(map(str, path))

3. 调用示例 #

# 示例：查找从1232到45678的最短路径
print(shortestRoute(1232, 45678, df))
# 输出示例：1232 -> 2342 -> 45678

注意事项 #

• 如果存在多条相同权重的最短路径，该实现会返回优先队列先搜索到的那一条
• 如果节点ID是字符串类型，只需要去掉预处理中把索引转成int的步骤即可
• 可以根据需求修改返回值，直接返回路径列表而非拼接后的字符串

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