为什么Dijkstra算法不能处理有负权值的图?

2025-04-09 05:25:39
推荐回答(1个)
回答1:

很简单
Dijkstra不断维护最小,每次走使当前权值最小的能边,那么一旦有负的权值
每次从这里通过总的权值和就会越来越小,那么这条边会一直是最小边,
Dijkstra算法会使你陷入死循环,不断在这条负权值的边两端的点来回
可以理解么?