机器学习实战应用案例100篇（二十六）-最短路径算法应用案例

Bellman Ford算法(单源最短路径)

1 算法简介

Bellman Ford算法帮助我们找到加权图中从一个顶点到所有其他顶点的最短路径。

它类似于Dijkstra算法，但它可以用于权边为负的图。

为什么在现实生活中会有负权边呢？

负权边一开始可能看起来毫无用处，但它们可以解释很多现象，比如现金流，化学反应中释放/吸收的热量，等等。

例如，如果从一种化学物质A到另一种化学物质B有不同的方法，每一种方法都会有涉及散热和吸收的子反应。

如果想要找到需要最小能量的反应集，那么就需要能够将热吸收作为负权重，热耗散作为正权重。

为什么要小心负权值呢？

负权边可以创建负权循环，即通过返回到同一点来减少总路径距离的循环。

最短路径算法，如Dijkstra's Algorithm，不能检测到这样的循环，可能会给出一个错