Dijkstra算法无法存储最短路径，求代码排查与路径实现方案

问题描述 #

已实现Dijkstra算法，可计算起始节点到所有节点的最短距离，但无法获取对应最短路径。参考YouTube视频自行用Python实现，未遵循标准伪代码，需排查代码问题并指导返回两节点间的最短路径。

原代码 #

def dijkstra(start_id: int,end_id:int,graph:Dict):
    '''
    TODO: Implement dijkstra, change the parameters if you wish so.
    '''
    #make a list for all of the paths
    paths = []
    # Is a list for all of the visited nodes 
    visited_nodes = []
    # make a table that stores all of the values of the nodes
    table = {v:float("inf") for v in graph}
    # Set the start id value in the table to 0
    table[start_id] = 0
    # Make the minimum that is going to be compared with equal to inifinity in the start
    minimum = float("inf")
    # The path should contain the start id at the start
    path = [start_id]
    # Make a while statement that the operation keeps going until every node is visited 
    while end_id not in visited_nodes:
        # Explore the edges of the node
        for edge in graph.get(path[-1]):
            #if edge == end_id:
            # If there is only one element in the path
            if len(path) <= 1:
                # We are going to compare it directly with itself not any before nodes
                if graph[path[-1]][edge] < table[edge]:
                    table[edge] = graph[path[-1]][edge]
            # This is the normal conditions         
            if len(path)> 1:
                # Compare the weight of this edge + the weigh of the previous edge 
                if graph[path[-1]][edge] + table[path[-2]] < table[edge]:
                    table[edge] = graph[path[-1]][edge] + table[path[-2]]
        # We then add the node to its edges were explored to the visited list
        visited_nodes.append(path[-1])
        # This is just added to be able to add the last node that was not explored
        if len(visited_nodes) < len(graph)-1:
            # Now we choose the next node to be explored, by looping through all the nodes in the set
            for node in table:
                # Only if the node is not in the visited list it will be explored
                if node not in visited_nodes:
                    if table[node] < minimum:
                        minimum = table[node]
                        minimum_node = node
            path.append(minimum_node)
        else:    
            # Will add the last node that was not added 
            for node in table:
                if node not in visited_nodes:
                    path.append(node)
        # print(minimum_node)
    paths.append(path)
    return table

代码问题分析 #

1. 缺少前驱节点记录：当前代码仅维护了一个path列表记录遍历顺序，而非实际最短路径的节点关联，无法回溯出从起点到终点的真实路径。
2. 距离更新逻辑错误：更新邻居节点距离时，错误使用了table[path[-2]]（前一个遍历节点的距离），正确逻辑应该是用当前节点的最短距离table[path[-1]]加上边权。
3. 最小值变量未重置：每次选择下一个节点前，minimum未重新设为无穷大，会导致后续选节点时沿用之前的最小值，无法选出当前未访问节点中的最短距离节点。
4. 路径存储无效：paths列表仅添加了遍历顺序的path，并非实际最短路径，没有意义。

解决方案与修改后代码 #

要获取最短路径，核心是新增前驱节点字典记录每个节点的上一个节点，最后从终点回溯到起点再反转得到路径。同时修正距离计算逻辑：

from typing import Dict, List

def dijkstra(start_id: int, end_id: int, graph: Dict) -> (Dict, List[int]):
    # 初始化距离表，所有节点初始为无穷大
    distance = {v: float("inf") for v in graph}
    distance[start_id] = 0
    # 前驱节点字典，记录每个节点的最短路径上的前一个节点
    predecessor = {v: None for v in graph}
    # 未访问节点集合
    unvisited = set(graph.keys())

    while unvisited:
        # 选择未访问节点中距离最小的节点
        current_node = min(unvisited, key=lambda node: distance[node])
        # 如果当前节点是终点，可提前终止
        if current_node == end_id:
            break
        # 标记为已访问
        unvisited.remove(current_node)
        # 遍历当前节点的所有邻居
        for neighbor, weight in graph[current_node].items():
            # 计算通过当前节点到邻居的距离
            new_distance = distance[current_node] + weight
            # 如果新距离更短，更新距离和前驱节点
            if new_distance < distance[neighbor]:
                distance[neighbor] = new_distance
                predecessor[neighbor] = current_node

    # 回溯生成最短路径
    shortest_path = []
    current = end_id
    while current is not None:
        shortest_path.append(current)
        current = predecessor[current]
    # 反转得到从起点到终点的路径
    shortest_path.reverse()

    # 如果路径起点不是start_id，说明无有效路径
    if shortest_path[0] != start_id:
        return distance, []
    
    return distance, shortest_path

使用说明 #

• 输入的graph需为字典格式，例如：{0: {1: 2, 2: 5}, 1: {0: 2, 3: 1}, 2: {0:5, 3:3}, 3: {1:1, 2:3}}
• 返回值包含两个部分：distance是起点到所有节点的最短距离字典，shortest_path是起点到终点的最短路径列表（无路径时返回空列表）

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