Jac*_*ale 8 algorithm graph data-structures
该算法设计手册说:
大多数图算法都不容易适应负数.实际上,最短路径算法在负数方面存在问题,并且当然不会使用这种技术生成尽可能长的路径.
但为什么？当我们-在原始重量前加上负数时,我认为大多数涉及重量的图形问题都可以平等对待,对吧？
因为当您考虑路径的最小或最大成本时,您总是最终考虑所有单个步骤的总和.
并且由于许多这些算法通过逐步选择最佳方法在本地工作(当然,具有不同幅度的步长),具有负权重将仅产生周期或误报.
具有负权重意味着路径的成本在未来可能会降低,这就是它产生问题的原因:即使在到达现在的路径更昂贵的点之后,您也无法从潜在的良好路径列表中排除路径因为你可以找到负重的边缘,这会改变这种情况.
举个例子:如果你有两个节点由两个权重边相互连接1,-2你可以在它们之间创建一个循环来确定一个任意低成本(偶数-?)的路径.
| 归档时间： |
|
| 查看次数： |
1311 次 |
| 最近记录： |