dijkstra为什么不能处理负权

dijkstra为什么不能处理负权,请解释.

2025-03-09 22:35:31

推荐回答（1个）

回答1：

dijkstra由于是贪心的，每次都找一个距源点最近的点（dmin），然后将该距离定为这个点到源点的最短路径（d[i]<--dmin）；但如果存在负权边，那就有可能先通过并不是距源点最近的一个次优点（dmin'），再通过这个负权边L(L<0)，使得路径之和更小（dmin'+L比如n=3，邻接矩阵：
0，3，4
3，0，-2
4，-2，0
用dijkstra求得d[1，2]=3，事实上d[1，2]=2，就是通过了1-3-2使得路径减小。不知道讲得清楚不清楚。
以上仅代表我个人的一些观点，未必正确，请大牛们指正。