数据结构 图 最短路径问题 迪杰斯特拉算法和弗洛伊德算法问题
题目
数据结构 图 最短路径问题 迪杰斯特拉算法和弗洛伊德算法问题
求解下面两句话都错在什么地方?
（1）求从指定原点到其余各顶点的迪杰斯特拉最短路径算法中弧上权值不能为负的原因是在实际应用中无意义
（2）弗洛伊德求每对不同顶点对的算法中允许弧上的权值为负,但不能有权值和为负的回路
答案
1.dijkstra 不能有负权边,否则结果是错的,你想想,假如无向图有1,2,3个点,w(1,2)=1,w(1,3)=2,w(2,3)=-2.按dij算法求求看.
2.这句话还没找到反例...不过教floyd时说是用在非负权边上的,除了负的回路之外应该还有漏洞吧..
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
- 七上《紫藤萝瀑布》人和花都会遇到各种各样的不幸,但是生命的长河是无止境的意思
- 1.有物体存在就一定存在力吗
- 致以良好的祝愿用英语怎么说?
- 已知全集u={1,2,3,4,5} A=｛x|x^2-5x+q=0｝,求A的补集（集合A中x的取值怎么算啊,
- 甲、乙两个注水管，单开甲管12小时注满一池水，单开乙管，15小时注满一池水，两管齐开同时注水，多少小时能注满一池水的3/4？
- 求一篇以我喜欢的体育明星为题的英语作文
- 已知点A(a,-2b)和点B（3-b,a-9）关于x轴对称,求ab的值
- I can find a picture in your desk.改为否定句 I ___ ___ find a pictuer in your desk.
- 有人用过“水宜生”的杯子吗?
- If only the committee _______ the regulations and put them into effect as s
热门考点
- 甲、乙两辆汽车从相距324千米的两地同时开出,相对开出,经过4小时相遇.甲车每小时行42千米,乙车每小时
- 三个5一个1,加.减.乘.除,随便用,结果等于24.怎么算/每个数字都只能用一次/
- 由离子构成的物质(除氯化钾)
- 被决定用英语怎么说
- 成语填空：（两字须重叠）
- 古文翻译”取时予名,查类明顾
- 设计一个坏事变好事的故事
- 一个体重六十千克的人,体内含水三十九千克,其他物质约21千克.人体中水和其他物质个占体重的百分之几?
- 一质点在x轴上并只朝着x轴的正方向运动,各个时刻的位置坐标如下表,则此质点开始运动后：
- 有a,b两数,如果b加5就等于a,此时两数的积就比原来两数的积多74,b数是多少?