如何在Python的Dijkstra算法中获取正确顺序的最短路径

我改写了一段Dijkstra算法的代码，现在需要实现存储每个节点最短路径的功能，但尝试后没能成功。以下是我的图类代码：

class Graph: 
    max_int = 999999
    def __init__(self, vertices, adj_matrix, start, target):
        # 获取顶点
        self.vertices = vertices
        self.start = start  # 起点的索引（整数）
        self.target = target # 目标节点的索引（整数）
        self.size = len(self.vertices)
        self.adj_matrix = adj_matrix  # 邻接矩阵

    def min_distance(self, distance, shortest_path_arr):
        min_distance = self.max_int
        min_index = 0
        for i in range(self.size):
            if distance[i] < min_distance and shortest_path_arr[i] == False:
                min_distance = distance[i]
                min_index = i
        
        return min_index
    
    def dijkstra(self):
        distance = [self.max_int] * self.size
        distance[self.start] = 0
        shortest_path_arr = [False] * self.size

        for vertex in range(self.size):
            x = self.min_distance(distance, shortest_path_arr)
            shortest_path_arr[x] = True

            for i in range(self.size):
                # 注意原代码拼写错误：adjMatrix -> adj_matrix
                if self.adj_matrix[x][i] > 0 and shortest_path_arr[i] == False and distance[i] > distance[x] + self.adj_matrix[x][i]:
                    distance[i] = distance[x] + self.adj_matrix[x][i]

解决方案 #

要获取正确顺序的最短路径，需要添加前驱节点追踪的逻辑，具体步骤如下：

1. 初始化前驱数组：在dijkstra方法中，创建parent数组，用于记录每个节点在最短路径上的前一个节点，初始值设为-1（表示无前置节点）。
2. 更新前驱节点：当更新某个节点的最短距离时，同步更新该节点的前驱为当前处理的节点。
3. 回溯生成路径：添加一个方法，从目标节点出发，沿着parent数组回溯到起点，再反转路径得到从起点到目标的正确顺序。

修改后的完整代码 #

class Graph: 
    max_int = 999999
    def __init__(self, vertices, adj_matrix, start, target):
        self.vertices = vertices
        self.start = start  # 起点索引
        self.target = target # 目标节点索引
        self.size = len(self.vertices)
        self.adj_matrix = adj_matrix  # 邻接矩阵

    def min_distance(self, distance, shortest_path_arr):
        min_distance = self.max_int
        min_index = 0
        for i in range(self.size):
            if distance[i] < min_distance and shortest_path_arr[i] == False:
                min_distance = distance[i]
                min_index = i
        
        return min_index
    
    def dijkstra(self):
        distance = [self.max_int] * self.size
        distance[self.start] = 0
        shortest_path_arr = [False] * self.size
        # 新增：前驱节点数组，记录每个节点的前一个节点
        self.parent = [-1] * self.size

        for vertex in range(self.size):
            x = self.min_distance(distance, shortest_path_arr)
            shortest_path_arr[x] = True

            for i in range(self.size):
                # 修正原代码的拼写错误
                if self.adj_matrix[x][i] > 0 and shortest_path_arr[i] == False and distance[i] > distance[x] + self.adj_matrix[x][i]:
                    distance[i] = distance[x] + self.adj_matrix[x][i]
                    # 新增：更新前驱节点
                    self.parent[i] = x
        return distance
    
    def get_shortest_path(self):
        # 从目标节点回溯到起点
        path = []
        current = self.target
        # 如果目标节点不可达，返回空路径
        if self.parent[current] == -1 and current != self.start:
            return []
        
        while current != -1:
            path.append(self.vertices[current])
            current = self.parent[current]
        # 反转路径，得到从起点到目标的顺序
        path.reverse()
        return path

使用示例 #

# 示例：顶点列表
vertices = ["A", "B", "C", "D", "E"]
# 邻接矩阵，0表示无连接
adj_matrix = [
    [0, 4, 0, 0, 0],
    [4, 0, 8, 0, 0],
    [0, 8, 0, 7, 0],
    [0, 0, 7, 0, 9],
    [0, 0, 0, 9, 0]
]
# 起点是A（索引0），目标是E（索引4）
g = Graph(vertices, adj_matrix, 0, 4)
distances = g.dijkstra()
path = g.get_shortest_path()

print("最短路径长度:", distances[g.target])
print("最短路径:", path)
# 输出：
# 最短路径长度: 28
# 最短路径: ['A', 'B', 'C', 'D', 'E']

关键点说明 #

• parent数组是核心：每个节点的前驱记录了最短路径中它的前一个节点，通过回溯可以还原路径。
• 处理不可达情况：如果目标节点的前驱始终是-1（且不是起点本身），说明该节点不可达，返回空路径。
• 路径反转：回溯得到的是从目标到起点的路径，反转后才是从起点到目标的正确顺序。

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