贝尔曼-福特算法
Sign in to saveAlso known as Bellman–Ford–Moore algorithm, Bellman-Ford equation, distance-vector routing algorithm
algorithm for finding single-source shortest paths in graphs, allowing some edge weights to be negative
Key facts
- Class
- Single-source shortest path problem (for weighted directed graphs)
- Data structure
- Graph
- Worst case performance
- Θ ( | V | | E | ) {\displaystyle \Theta (|V||E|)}
- Best case performance
- Θ ( | E | ) {\displaystyle \Theta (|E|)}
- Worst case space complexity
- Θ ( | V | ) {\displaystyle \Theta (|V|)}
via Wikipedia infobox
Article · 中文
贝尔曼-福特算法（英語：Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·貝尔曼（Richard Bellman） 和 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 也为这个算法的发展做出了贡献。它的原理是对图进行次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达。但算法可以进行若干种优化，提高了效率。
Abstract from DBpedia / Wikipedia · CC BY-SA