首页 > 试题广场 >

只要在无向有权图中存在1个环（回路）的权值之和为负值，我们就

[单选题]

只要在无向有权图中存在1个环（回路）的权值之和为负值，我们就称此无向图存在“负权回路”下面哪个算法可以检验一个无向图是否存在负权回路？ 

  • 最短路径 Bellman-Ford 算法
  • 最小生成树 Kruskal 算法
  • 最小生成树 Prim 算法
  • 最短路径 Dijkstra 算法
查看正确选项
添加回答
女。。。头像 女。。。
大题没办法选择选项吗？
发表于 2017-11-26 20:17:33 回复(0)
小威羊头像 小威羊
Bellman Ford 算法  可以存在负权边的情况下解决单源最短路问题和,当出现负权回路时返回布尔值0，不然，则返回1，并可以源点到各点输出最短路径
发表于 2017-08-15 10:37:36 回复(1)
言午111111111头像 言午111111111
B,C,D都是生成树的，自然测不出回路
发表于 2017-09-07 19:50:23 回复(1)
看见我请叫我去刷题头像 看见我请叫我去刷题
Bellman ford算法有负权回路返回0
发表于 2022-04-07 09:41:09 回复(0)
牛客313601546号头像 牛客313601546号
Bellman是求含负权图的单源最短路经的一种算法，效率较低．其原理为连续进行松弛在每次松张时都要把边都更新一下、若在n一1次松张后还能更新新、则说明图中有负环。
发表于 2021-11-05 13:11:12 回复(0)
提交观点

问题信息

C++工程师 2017 搜狗 图
来自：搜狗2017校招C++...
上传者：阿奻_
难度：
5条回答 6229浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号