作业帮dijkstra算法为什么不能处理边权值负数的情况,哪位师兄师姐解释下.清晰的有不少于20的加分.
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/03 21:39:17
dijkstra算法为什么不能处理边权值负数的情况,哪位师兄师姐解释下.清晰的有不少于20的加分.
dijkstra算法为什么不能处理边权值负数的情况,哪位师兄师姐解释下.清晰的有不少于20的加分.
dijkstra算法为什么不能处理边权值负数的情况,哪位师兄师姐解释下.清晰的有不少于20的加分.
楼上正解,你找个图自己用此算法实践一下就知道了,从A点出发,发现离A最近的点是B点,那么我们就已经认为A到B的最短距离就是AB了,如果有负数,就指不定冒出个C点,AC+CB
而且一般权值为负的图研究也比较少.有些带负权的图,某些点间还没有最小距离呢.中间出个带某条负权很大的边的环圈,绕此一圈所经过的距离反而减少了,那就一直在此圈上绕啊绕啊绕到负的足够大溢出为止.
当然考虑各种自己随便假设出来的变种问题也是很有趣的.比如说边带有多个权值对应多次经过改变的消费,上面的问题有可能变成有解的.话说那个站会后悔,第二次经过它会收回100万,第三次经过收回250万,这样的话你只需要经过一次就够了,问题也是有解的.再比如说对于多权重图,从A点出发经过B点到达C点的最短路线,就不是简单的AB最短路线+BC最短路线了,说不定两者有重合边,第二次经过来个天价就傻眼了.其实这种图貌似应该可以转化成单权重图的,我直觉估计啊,刚随便想出这个问题,还没去思考这个问题的解^_^
因为负边会破坏dijkstra的贪心假设。
问一下为什么dijkstra算法不能处理负权边.最好举例说明啊,越仔细越好...
dijkstra算法为什么不能处理边权值负数的情况,哪位师兄师姐解释下.清晰的有不少于20的加分.
单源最短路Dijkstra算法为什么权不能为负数
为什么Dijkstra算法含有负数的时候不正确
Dijkstra 算法是什么?Dijkstra 在哪里用
dijkstra算法是什么?迪杰斯特拉算法是什么?
Floyd算法与Dijkstra算法的不同
Kruskal 算法与Dijkstra算法区别
最短路径的Dijkstra算法思路
用C#求dijkstra算法求最短路径
Dijkstra算法的主要步骤是什么?
提供几道Dijkstra算法的ACM水题练习
求文档:Dijkstra 距离寻优算法程序
关于Matlab Dijkstra算法问题,麻烦帮我解释下,
图论有哪些算法?除了floyd Dijkstra之外,具体点
dijkstra算法是深度优先还是广度优先?
我的dijkstra算法怎么有问题部分数据不能运行 用matlab做的B第一列是编号 第二列是横坐标 第三列是纵坐标 A是连接矩阵 C是由AB算出的连接矩阵 问问为什么一部分数据可以算例如distram(C,14,25)
图论-关于dijkstra算法,在dijkstra算法中如果一个顶点到其他相邻点的距离都相等,那该选哪个点?