贝尔曼-福特算法
維基百科,自由的 encyclopedia
贝尔曼-福特算法(英語:Bellman–Ford algorithm),求解单源最短路径问题的一种算法,由理查德·貝尔曼和小萊斯特·倫道夫·福特创立。有时候这种算法也被称为貝爾曼-福特-摩爾算法(Bellman–Ford–Moore algorithm),因为愛德華·F·摩爾也为这个算法的发展做出了贡献。它的原理是对图进行次松弛操作,得到所有可能的最短路径。其优于戴克斯特拉算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达。但算法可以进行若干种优化,提高了效率。