数据结构 图 最短路径问题 迪杰斯特拉算法和弗洛伊德算法问题

数据结构 图 最短路径问题 迪杰斯特拉算法和弗洛伊德算法问题

题目
数据结构 图 最短路径问题 迪杰斯特拉算法和弗洛伊德算法问题
求解下面两句话都错在什么地方?
(1)求从指定原点到其余各顶点的迪杰斯特拉最短路径算法中弧上权值不能为负的原因是在实际应用中无意义
(2)弗洛伊德求每对不同顶点对的算法中允许弧上的权值为负,但不能有权值和为负的回路
答案
1.dijkstra 不能有负权边,否则结果是错的,你想想,假如无向图有1,2,3个点,w(1,2)=1,w(1,3)=2,w(2,3)=-2.按dij算法求求看.
2.这句话还没找到反例...不过教floyd时说是用在非负权边上的,除了负的回路之外应该还有漏洞吧..
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
1,人们染上烟瘾,最终因吸烟使自己丧命.
最新试题
热门考点

超级试练试题库

© 2017-2019 超级试练试题库,All Rights Reserved.