知识卡片

普通读书笔记卡 · 3644.h.17 · 生成模型:未记录

负边路径需要检测可达负环

理解等级:中级

Bellman-Ford可处理负权边;对从源可达且能影响目标的负权环,路径可反复绕环降低代价,因此该目标不存在有限最短路径。支持负边并不意味着所有含负环的输入都有有限答案。

书中给O(VE)与单源问题定位,未展开具体负环检测代码;实际结果应区分不可达、有限距离和受负环影响的顶点。全对最短路径可多次调用单源算法,也可依据图性质采用专门算法。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      Bellman-Ford算法 解决单源最短路径问题的另一种方法。与Kijkstra算法不同,Bellman-Ford算法支持边权值为负的图。其时间复杂度为O(VE),其中V是图中顶点的个数,E为边的条数。 Kruskal算法 另一种计算最小生成树的算法。其算法原理如下。首先,将每个顶点放入其自身的数

    参考来源

    - 位置:《算法精解:C语言描述》第16章《相关主题》(spine1420;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1386.html;u306-ch16-018)。 - 结论依据:306 Bellman-Ford和全对路径短段全文实读;负环后果为路径代价的直接推导。 - 原始内容:Bellman-Ford算法 解决单源最短路径问题的另一种方法。与Kijkstra算法不同,Bellman-Ford算法支持边权值为负的图。其时间复杂度为O(VE),其中V是图中顶点的个数,E为边的条数。 Kruskal算法 另一种计算最小生成树的算法。其算法原理如下。首先,将每个顶点放入其自身的数