题目

数据结构 图 最短路径问题 迪杰斯特拉算法和弗洛伊德算法问题
求解下面两句话都错在什么地方?
（1）求从指定原点到其余各顶点的迪杰斯特拉最短路径算法中弧上权值不能为负的原因是在实际应用中无意义
（2）弗洛伊德求每对不同顶点对的算法中允许弧上的权值为负,但不能有权值和为负的回路

提问时间：2021-02-19

答案

1.dijkstra 不能有负权边,否则结果是错的,你想想,假如无向图有1,2,3个点,w(1,2)=1,w(1,3)=2,w(2,3)=-2.按dij算法求求看.
2.这句话还没找到反例...不过教floyd时说是用在非负权边上的,除了负的回路之外应该还有漏洞吧..