Extra
精选上位词
贝尔曼-福特算法
简介
贝尔曼-福特算法(bellman-ford)是由理查德·贝尔曼(richard bellman)和 莱斯特·福特 创立的,求解单源最短路径问题的一种算法。有时候这种算法也被称为 moore-bellman-ford 算法,因为 edward f. moore 也为这个算法的发展做出了贡献。它的原理是对图进行v-1次松弛操作,得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达o(ve)。但算法可以进行若干种优化,提高了效率。
| 上位词 | 一种算法 |
|---|---|
| 中文名 | 贝尔曼-福特算法 |
| 原始名称 | 贝尔曼-福特算法 |
| 外文名 | bellman-ford |