突然发现自从上次搞崩了博客之后就很少再写博客了啥的。不过确实没啥好写的啦。
一直想着每天写写日记的来着,最终不了了之。
我就是这么一个永远静不下心来的人吧。
求最短路的算法之一,类似于Dijkstra算法,对于每一个点集中的点v,逐步减少起点s到v的最短路长度的估计值,知道达到其最短路径值。同时,Bellman-ford算法还会返回一个bool类型的值如果不存在从s可达到的负权回路就返回true,否则false,这样就能够在存在负权边的情况下解决单源最短路的问题,这点上比Dijkstra算法要优。由于该算法更多的是对边进行操作,因此能更高效地解决稀疏图的最短路问题。算法复杂度Θ(V*E)。