Dijkstra算法出现list index out of range错误的排查与修复咨询

错误原因 #

list index out of range 错误出现在 temp = min_heap[0][1] 行，本质是尝试访问空列表的第一个元素。具体诱因有三：

1. 固定次数循环: 代码强制执行38次循环，当所有可达节点处理完毕后，min_heap 会变为空，但循环仍继续运行，导致访问空堆。
2. 堆管理逻辑缺陷: 仅当 temp 未被访问时才初始化并填充 min_heap，若 temp 已访问，min_heap 沿用之前的状态，可能为空。
3. 图结构错误: 你的 graph 中存在重复的 AI 节点定义，后一个 'AI':{'AJ':52} 覆盖了前一个包含多邻居的 AI 条目，导致节点连接关系错误；同时缺失 AL 节点的图条目，但 node_data 中却包含该节点，会引发后续访问异常。

原作者调试建议的含义 #

原作者建议每次迭代用 print() 分析列表及访问方式，具体是指在关键步骤添加打印语句，追踪以下内容：

• 当前迭代的 temp 节点
• visited 列表的内容，确认哪些节点已被处理
• min_heap 的实时状态，观察何时变为空
• node_data 中各节点的 cost 和 pred 值，验证路径更新是否符合预期

通过这些打印信息，你可以直观看到算法执行到哪一步时 min_heap 为空，以及节点访问顺序是否正常，从而精准定位问题根源。

修复方案 #

1. 修复图结构错误 #

• 删除 graph 中重复的 'AI':{'AJ':52} 行，并将 AJ 添加到原 AI 的邻居列表中
• 补充 AL 节点的空邻居条目，避免键不存在的错误

修正后的关键条目示例：

'AI': {'AE':82.2, 'AF':181.2, 'AK':110, 'AJ':52},
'AL': {},

2. 重构Dijkstra算法逻辑 #

调整循环方式，改用优先队列标准操作（heappop），并处理空堆及不可达节点的情况：

import sys
from heapq import heappush, heappop

def dijsktra(graph, src, dest):
    inf = sys.maxsize
    # 从图节点自动生成node_data，避免手动维护错误
    node_data = {node: {'cost': inf, 'pred': []} for node in graph}
    node_data[src]['cost'] = 0
    visited = []
    # 初始化优先队列，放入起点
    min_heap = []
    heappush(min_heap, (node_data[src]['cost'], src))
    
    while min_heap:
        # 弹出当前成本最小的节点
        current_cost, temp = heappop(min_heap)
        # 若已访问过，跳过重复处理
        if temp in visited:
            continue
        visited.append(temp)
        # 遍历当前节点的所有邻居
        for neighbor, weight in graph[temp].items():
            if neighbor not in visited:
                new_cost = current_cost + weight
                if new_cost < node_data[neighbor]['cost']:
                    node_data[neighbor]['cost'] = new_cost
                    node_data[neighbor]['pred'] = node_data[temp]['pred'] + [temp]
                    heappush(min_heap, (new_cost, neighbor))
    
    # 判断目标节点是否可达
    if node_data[dest]['cost'] == inf:
        print(f"从 {src} 到 {dest} 没有可达路径")
    else:
        print("最短距离: " + str(node_data[dest]['cost']))
        print("最短路径: " + str(node_data[dest]['pred'] + [dest]))

3. 完整修复代码 #

import sys
from heapq import heappush, heappop

def dijsktra(graph, src, dest):
    inf = sys.maxsize
    node_data = {node: {'cost': inf, 'pred': []} for node in graph}
    node_data[src]['cost'] = 0
    visited = []
    min_heap = []
    heappush(min_heap, (node_data[src]['cost'], src))
    
    while min_heap:
        current_cost, temp = heappop(min_heap)
        if temp in visited:
            continue
        visited.append(temp)
        for neighbor, weight in graph[temp].items():
            if neighbor not in visited:
                new_cost = current_cost + weight
                if new_cost < node_data[neighbor]['cost']:
                    node_data[neighbor]['cost'] = new_cost
                    node_data[neighbor]['pred'] = node_data[temp]['pred'] + [temp]
                    heappush(min_heap, (new_cost, neighbor))
    
    if node_data[dest]['cost'] == inf:
        print(f"从 {src} 到 {dest} 没有可达路径")
    else:
        print("最短距离: " + str(node_data[dest]['cost']))
        print("最短路径: " + str(node_data[dest]['pred'] + [dest]))


if __name__ == "__main__":
    graph = {
        'A': {'D':105.3},
        'B': {'E':65},
        'C': {'AM':103.4},
        'D': {'A':105.3,'E':132.8,'J':165.8},
        'E': {'B':65,'D':132.8,'F':176.6,'H':78.3},
        'F': {'E':176.6,'R':181.8,'AM':20.3},
        'G': {'H':63,'K':57.2},
        'H': {'E':78.3,'G':63,'I':65,'O':101.2},
        'I': {'H':65,'P':104},
        'J': {'D':165.8,'K':125.6,'L':25.9},
        'K': {'G':57.2,'J':125.6,'N':37.5},
        'L': {'J':25.9,'M':68,'Y':177.7},
        'M': {'L':25.9,'N':56,'V':124},
        'N': {'K':37.5,'M':56,'O':77.4},
        'O': {'H':101.2,'N':77.4,'P':70.2,'W':128.6},
        'P': {'I':104,'O':70.2,'Q':68},
        'Q': {'P':68,'R':45,'T':102.9},
        'R': {'F':181.8,'Q':45,'S':51},
        'S': {'R':51,'U':104.3,'AM':193.3},
        'T': {'Q':102.9,'U':84.35,'X':21.6},
        'U': {'S':104.3,'A':84.35,'AF':160.7},
        'V': {'M':124,'W':128,'Z':45},
        'W': {'O':128.6,'V':128,'X':150.7,'AD':132.9},
        'X': {'T':21.6,'W':150.7,'AE':166.8},
        'Y': {'L':177.7,'Z':100.9,'AA':39.8},
        'Z': {'V':45,'Y':100.9,'AB':34},
        'AA': {'Y':39.8,'AB':100.3,'AH':258.5},
        'AB': {'Z':34,'AA':100.3,'AC':47.8},
        'AC': {'AB':47.8,'AD':126,'AH':60.37},
        'AD': {'W':132.9,'AE':110.2,'AK':93.14,'AC':126},
        'AE': {'X':166.8,'AI':82.2,'AD':110.2},
        'AF': {'U':160.7,'AG':13.7,'AI':181.2},
        'AG': {'AF':13.7},
        'AH': {'AA':285.5,'AC':60.37,'AJ':33.8},
        'AI': {'AE':82.2,'AF':181.2,'AK':110,'AJ':52},
        'AJ': {'AH':33.8,'AK':119.3,'AL':52},
        'AK': {'AD':93.14,'AI':110,'AJ':119.3},
        'AL': {},
        'AM': {'C':103.4,'S':193.3,'F':20.3}
    }

    source = 'A'
    destination = 'F'
    dijsktra(graph, source, destination)

关键改进点 #

• 自动从图节点生成 node_data，避免手动维护的遗漏或错误
• 使用 heappop 正确获取优先队列中的最小成本节点
• 循环直到优先队列为空，不再依赖固定次数
• 添加不可达路径的判断逻辑
• 修复了图中重复节点定义及缺失节点的问题

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