使用Dijkstra算法计算建筑最短路径时遇KeyError:0问题求助

问题描述 #

我尝试用Dijkstra算法计算某一特定建筑到其他所有建筑的最短距离，但代码运行时触发如下错误：

Traceback (most recent call last):
File "main.py", line 26, in dijkstra
for v in self.graph[u]:
KeyError: 0

我猜测问题可能和图的顶点是字符串类型而非整数有关，但认为算法仅需比较路径数值，不应受此影响，希望得到问题定位和修正指导。

原代码 #

import sys 
  
class Graph(): 
  
  def __init__(self, vertices): 
    self.V = vertices 
    self.graph = {}
    
  def min_distance(self,distance,traversed):
    min_index = 0 
    min_value = sys.maxsize
    for i in range(self.V):
      if traversed[i] is False and min_value > distance[i]:
        min_value = distance[i]
        min_index = i
    return min_index
    
  def dijkstra(self,source):
    distance = [sys.maxsize] * self.V
    traversed = [False] * self.V
    distance[source] = 0
        
    for i  in range(self.V):
      u = self.min_distance(distance,traversed)
      traversed[u] = True
      for v in self.graph[u]:               #ERROR
        if(traversed[v] is False):
          distance[v] = min(distance[v],distance[u]+self.graph[u][v])
    print("from the give source vertex -- > ",source)
    for vertex in range(self.V):
      print("Vertex ",vertex," --> Distance = ",distance[vertex])
                
g  = Graph(19)

g.graph = {
    'College Square':{'Lewis Science Center':200, 'Prince Center':300},
    'Lewis Science Center':{'College Square':200, 'Speech Language Hearing':250, 'Computer Science':150},
    'Speech Language Hearing':{'Lewis Science Center':250, 'Burdick':100, 'Maintenance College':120},
    'Computer Science':{'Prince Center':80, 'Torreyson Library':40, 'Burdick':30, 'Lewis Science Center':150},
    'Burdick':{'Computer Science':30, 'Speech Language Hearing':100, 'Torreyson Library':80, 'Maintenance College':300, 'McALister Hall':200},
    'Prince Center':{'College Square':300, 'Computer Science':80, 'Torreyson Library':30, 'Police Dept.':100},
    'Torreyson Library':{'Prince Center':30, 'Computer Science':40, 'Burdick':80, 'Old Main':30},
    'Old Main':{'Torreyson Library':30, 'Police Dept.':200, 'Fine Art':90, 'McALister Hall':100},
    'Maintenance College':{'Speech Language Hearing':120, 'Burdick':300, 'McALister Hall':150, 'Wingo':100, 'New Business Building':150, 'Oak Tree Apt.':160},
    'Police Dept.':{'Prince Center':100, 'Old Main':200, 'Fine Art':50, 'Student Health Center':100},
    'Fine Art':{'Police Dept.':50, 'Old Main':90, 'McALister Hall':180, 'Student Center':80},
    'McALister Hall':{'Fine Art':180, 'Old Main':100, 'Burdick':200, 'Maintenance College':150, 'Wingo':50, 'Student Center':100},
    'Student Center':{'Fine Art':80, 'McALister Hall':100, 'Wingo':100, 'New Business Building':110, 'Student Health Center':50},
    'Wingo':{'Student Center':100, 'McALister Hall':50, 'Maintenance College':100, 'New Business Building':50},
    'Student Health Center':{'Police Dept.':100, 'Student Center':50, 'Brewer-Hegeman':200},
    'New Business Building':{'Student Center':110, 'Wingo':50, 'Maintenance College':150, 'Oak Tree Apt.':30, 'Brewer-Hegeman':20},
    'Oak Tree Apt.':{'Maintenance College':160, 'New Business Building':30, 'Brewer-Hegeman':40},
    'Brewer-Hegeman':{'Student Health Center':200, 'New Business Building':20, 'Oak Tree Apt.':40, 'Bear village Apt.':350},
    'Bear village Apt.':{'Brewer-Hegeman':350}

     }

g.dijkstra(0)

问题定位 #

你的代码核心矛盾是混用了整数索引和字符串顶点标识：

• 图self.graph的键是字符串（建筑名称），但min_distance方法返回的是0~18的整数索引，用这个整数去self.graph中查找键，必然找不到，触发KeyError。
• distance和traversed数组是按整数索引维护的，但你的顶点是字符串，两者没有对应关系，后续的距离更新、遍历标记逻辑全错。

修复方案 #

我们需要建立字符串顶点和整数ID的双向映射，让算法用整数ID处理逻辑，同时保留字符串名称用于结果输出：

1. 在Graph类中添加顶点名称与ID的映射字典；
2. 初始化时将字符串格式的图转换为整数ID格式；
3. 修改min_distance和dijkstra方法，适配ID映射逻辑；
4. 输出结果时将ID转回建筑名称，提升可读性。

修正后完整代码 #

import sys 
  
class Graph(): 
  
    def __init__(self, graph): 
        # 建立顶点名称到ID的映射，以及反向映射
        self.vertex_names = list(graph.keys())
        self.name_to_id = {name: idx for idx, name in enumerate(self.vertex_names)}
        self.id_to_name = {idx: name for idx, name in enumerate(self.vertex_names)}
        self.V = len(self.vertex_names)
        
        # 将字符串格式的图转换为整数ID格式
        self.graph = {}
        for u_name, neighbors in graph.items():
            u_id = self.name_to_id[u_name]
            self.graph[u_id] = {}
            for v_name, weight in neighbors.items():
                v_id = self.name_to_id[v_name]
                self.graph[u_id][v_id] = weight
    
    def min_distance(self, distance, traversed):
        min_index = -1 
        min_value = sys.maxsize
        for i in range(self.V):
            if not traversed[i] and distance[i] < min_value:
                min_value = distance[i]
                min_index = i
        return min_index
    
    def dijkstra(self, source_name):
        # 将源点名称转换为ID
        source = self.name_to_id[source_name]
        distance = [sys.maxsize] * self.V
        traversed = [False] * self.V
        distance[source] = 0
            
        for _ in range(self.V):
            u = self.min_distance(distance, traversed)
            # 处理所有顶点都已遍历的边界情况
            if u == -1:
                break
            traversed[u] = True
            # 遍历当前顶点的所有邻接顶点
            for v, weight in self.graph[u].items():
                if not traversed[v] and distance[u] != sys.maxsize:
                    if distance[v] > distance[u] + weight:
                        distance[v] = distance[u] + weight
        
        # 输出格式化结果
        print(f"从源点 {source_name} 出发的最短距离：")
        for idx in range(self.V):
            dist = distance[idx] if distance[idx] != sys.maxsize else "不可达"
            print(f"建筑 {self.id_to_name[idx]} --> 距离 = {dist}")
                
# 定义原始图结构
original_graph = {
    'College Square':{'Lewis Science Center':200, 'Prince Center':300},
    'Lewis Science Center':{'College Square':200, 'Speech Language Hearing':250, 'Computer Science':150},
    'Speech Language Hearing':{'Lewis Science Center':250, 'Burdick':100, 'Maintenance College':120},
    'Computer Science':{'Prince Center':80, 'Torreyson Library':40, 'Burdick':30, 'Lewis Science Center':150},
    'Burdick':{'Computer Science':30, 'Speech Language Hearing':100, 'Torreyson Library':80, 'Maintenance College':300, 'McALister Hall':200},
    'Prince Center':{'College Square':300, 'Computer Science':80, 'Torreyson Library':30, 'Police Dept.':100},
    'Torreyson Library':{'Prince Center':30, 'Computer Science':40, 'Burdick':80, 'Old Main':30},
    'Old Main':{'Torreyson Library':30, 'Police Dept.':200, 'Fine Art':90, 'McALister Hall':100},
    'Maintenance College':{'Speech Language Hearing':120, 'Burdick':300, 'McALister Hall':150, 'Wingo':100, 'New Business Building':150, 'Oak Tree Apt.':160},
    'Police Dept.':{'Prince Center':100, 'Old Main':200, 'Fine Art':50, 'Student Health Center':100},
    'Fine Art':{'Police Dept.':50, 'Old Main':90, 'McALister Hall':180, 'Student Center':80},
    'McALister Hall':{'Fine Art':180, 'Old Main':100, 'Burdick':200, 'Maintenance College':150, 'Wingo':50, 'Student Center':100},
    'Student Center':{'Fine Art':80, 'McALister Hall':100, 'Wingo':100, 'New Business Building':110, 'Student Health Center':50},
    'Wingo':{'Student Center':100, 'McALister Hall':50, 'Maintenance College':100, 'New Business Building':50},
    'Student Health Center':{'Police Dept.':100, 'Student Center':50, 'Brewer-Hegeman':200},
    'New Business Building':{'Student Center':110, 'Wingo':50, 'Maintenance College':150, 'Oak Tree Apt.':30, 'Brewer-Hegeman':20},
    'Oak Tree Apt.':{'Maintenance College':160, 'New Business Building':30, 'Brewer-Hegeman':40},
    'Brewer-Hegeman':{'Student Health Center':200, 'New Business Building':20, 'Oak Tree Apt.':40, 'Bear village Apt.':350},
    'Bear village Apt.':{'Brewer-Hegeman':350}
}

# 创建图实例并运行Dijkstra算法，传入源点名称
g = Graph(original_graph)
g.dijkstra('College Square')

关键修改说明 #

• 初始化时自动生成顶点名称与ID的双向映射，无需手动维护顶点数量；
• 将原始字符串图转换为整数ID格式，适配算法的整数索引逻辑；
• dijkstra方法接收字符串类型的源点名称，更符合业务场景；
• 输出结果显示建筑名称，而非抽象的ID，可读性更强；
• 增加了边界处理，避免所有顶点遍历完成后出现无效索引。

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