问题是您没有从队列中删除所有顶点实例 => 相同的顶点可以多次添加到结果中。
假设如下图:
weight(0,1) = 1
weight(0,2) = 2
weight(1,2) = 3
weight(1,3) = 4
weight(2,3) = 5
在“第一次迭代”之后,队列包含 PriorityVertex(1, 1)、PriorityVertex(2, 2)。
while 循环的迭代:
1) removed: PriorityVertex(1, 1) - edge (0,1)
added: PriorityVerterx(2, 3) and PriorityVertex(3, 4)
queue: PriorityVertex(2, 2), PriorityVertex(2, 3), PriorityVertex(3, 4)
2) removed: PriorityVertex(2, 2) - edge (0,2)
added: PriorityVertex(3, 5)
queue: PriorityVertex(2, 3), PriorityVertex(3, 4), PriorityVertex(3, 5)
3) removed: PriorityVertex(2, 3) - edge (1,2), cycle in the result!