实现Dijkstra最短路径算法时遇<运算符不支持错误求助

AI 小北

2026-8-20

Dijkstra算法实现中的<运算符比较错误

问题背景

在给定图结构上实现Dijkstra算法时触发错误，核心是无法对Vertex类实例使用<运算符进行比较。

图数据

(a, b, 7)、(a, c, 9)、(a, f, 14)
(b, a, 7)、(b, c, 10)、(b, d, 15)
(c, a, 9)、(c, b, 10)、(c, d, 11)、(c, f, 2)
(d, b, 15)、(d, c, 11)、(d, e, 6)
(e, d, 6)、(e, f, 9)
(f, a, 14)、(f, c, 2)、(f, e, 9)

报错回溯

Traceback (most recent call last):
  File "e:\Graph Theory\DijestraShortestPath.py", line 156, in 
    dijkstra(g, g.get_vertex('a'), g.get_vertex('e'))
  File "e:\Graph Theory\DijestraShortestPath.py", line 95, in dijkstra
    heapq.heapify(unvisited_queue)
TypeError: '<' not supported between instances of 'Vertex' and 'Vertex'

关联代码片段

if new_dist < next.get_distance():

错误触发在调用heapq.heapify(unvisited_queue)时。

问题根源

Python的heapq模块做堆化操作时，会自动对元素做排序比较。而你的unvisited_queue里直接放的是Vertex类的实例，自定义类默认没实现<运算符的比较规则，堆化时没法判断两个Vertex实例的大小，所以抛出这个TypeError。

两种解决办法

改堆存储的元素结构：别直接存Vertex实例，换成(当前距离, Vertex实例)的元组。元组比较会先按第一个元素（距离）排序，距离相同才会比第二个元素，这样就能用Python内置的元组比较逻辑完成堆排序。
调整示例：
```
# 初始化堆的时候
unvisited_queue = [(v.get_distance(), v) for v in graph]
heapq.heapify(unvisited_queue)
```
给Vertex类加比较方法：在Vertex类里定义__lt__方法，指定用距离来做比较，让heapq能正确对比实例。
示例代码：
```
class Vertex:
    # 你的其他代码...
    def __lt__(self, other):
        return self.get_distance() < other.get_distance()
```