Python用heapq实现Dijkstra算法堆化元组列表Vertex实例比较报错

报错原因 #

Python的heapq模块比较元组元素时，会按元组索引顺序依次比较值：如果两个元组的第一个元素相等，就会自动比较第二个元素。你当前堆里的元素是(距离, Vertex对象)，当多个顶点的距离相等时，就会触发两个Vertex实例的比较逻辑，而你没有给Vertex类定义<对应的比较运算符，就会抛出该错误。

解决方案 #

有两种修改方案，选任意一种即可：

方案一：修改堆元素结构，避免比较Vertex对象 #

构造堆元素时，在距离和Vertex对象之间插入一个可比较的唯一值（比如顶点ID），这样即使距离相等也只会比较ID，永远不会触发Vertex实例的比较，改法最小：

1. 修改Dijkstra函数中构造unvisitedQueue的两处代码：

# 原写法
unvisitedQueue = [(v.getDistance(), v) for v in G]
# 替换为
unvisitedQueue = [(v.getDistance(), v.getVertex_ID(), v) for v in G]

# 后续过滤已访问节点的构造逻辑也对应修改
unvisitedQueue = [(v.getDistance(), v.getVertex_ID(), v) for v in G if v not in visited]

2. 修改取出当前顶点的逻辑：

# 原写法
uv = heapq.heappop(unvisitedQueue)
currVert = uv[1]
# 替换为
uv = heapq.heappop(unvisitedQueue)
currVert = uv[2]

方案二：给Vertex类添加比较运算符 #

在Vertex类中新增__lt__方法，自定义两个Vertex实例的比较规则：

class Vertex:
    # 原有代码全部保留，新增以下方法
    def __lt__(self, other):
        # 按顶点ID比较即可，可按需调整规则
        return self.id < other.id

额外注意 #

你粘贴的代码里的<、"是HTML转义字符，实际运行时需要替换回对应的原生符号<、"，否则会触发语法错误。

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