题目

dijkstra算法为什么不能处理边权值负数的情况,哪位师兄师姐解释下.清晰的有不少于20的加分.

提问时间：2021-03-28

答案

楼上正解,你找个图自己用此算法实践一下就知道了,从A点出发,发现离A最近的点是B点,那么我们就已经认为A到B的最短距离就是AB了,如果有负数,就指不定冒出个C点,AC+CB简单说来,你驾车从家出发到某地沿某条路只需经过一个收费站,但是远在外省某地有个站不但不收你的费,你去了还会给你个千八百万的欢迎光临费,你能说你直接沿着这条路去某地是最省费用的?不计时间成本,绕到外省那个给你钱的地方,再绕回到你的目的地,还能赚钱呢.
而且一般权值为负的图研究也比较少.有些带负权的图,某些点间还没有最小距离呢.中间出个带某条负权很大的边的环圈,绕此一圈所经过的距离反而减少了,那就一直在此圈上绕啊绕啊绕到负的足够大溢出为止.
当然考虑各种自己随便假设出来的变种问题也是很有趣的.比如说边带有多个权值对应多次经过改变的消费,上面的问题有可能变成有解的.话说那个站会后悔,第二次经过它会收回100万,第三次经过收回250万,这样的话你只需要经过一次就够了,问题也是有解的.再比如说对于多权重图,从A点出发经过B点到达C点的最短路线,就不是简单的AB最短路线+BC最短路线了,说不定两者有重合边,第二次经过来个天价就傻眼了.其实这种图貌似应该可以转化成单权重图的,我直觉估计啊,刚随便想出这个问题,还没去思考这个问题的解^_^