而且一般权值为负的图研究也比较少.有些带负权的图,某些点间还没有最小距离呢.中间出个带某条负权很大的边的环圈,绕此一圈所经过的距离反而减少了,那就一直在此圈上绕啊绕啊绕到负的足够大溢出为止.
当然考虑各种自己随便假设出来的变种问题也是很有趣的.比如说边带有多个权值对应多次经过改变的消费,上面的问题有可能变成有解的.话说那个站会后悔,第二次经过它会收回100万,第三次经过收回250万,这样的话你只需要经过一次就够了,问题也是有解的.再比如说对于多权重图,从A点出发经过B点到达C点的最短路线,就不是简单的AB最短路线+BC最短路线了,说不定两者有重合边,第二次经过来个天价就傻眼了.其实这种图貌似应该可以转化成单权重图的,我直觉估计啊,刚随便想出这个问题,还没去思考这个问题的解^_^