如果最短的航线有许多，那么你可能解决了错误的问题。例如，如果我们希望减少油料消耗，那么自然而然我们会选择最短路径。但是在着陆和起飞时油料消耗也是必须考虑的因素。你必须考虑到起飞和降落时额外的油料消耗，并且把这个额外的消耗加入到distance（say，D）中。然后再寻找最短路径。
在这个问题上，我们能够找到最短路径。在其他的应用中，我们可以用时间（例如在网络中尽可能快速地投递网络包）或者开销（例如商务旅行中寻找最便宜的从S t.Johnsbury去Waco的交通工具）代替距离。这些问题同样也可以抽象成最短路径。
如果我们需要在网络的两点之间传递数据包，在我们已经知道正确传递数据包的概率，那么寻找到最可靠的路径很有必要。路径正确传递数据包的概率是每条边的概率之积。我们创建一个新图，每条边的概率将原图中的概率取负对数。这样，在这个新图中，最短路径就是原图中的最可靠路径。
Dijkstra算法不能够应用于有负权边的图。但是，Bellman-Ford（如图6-16和例6-6所示）可以在不存在负值环的情况下使用。也就是说，不存在一个环，其边权值总和为负数。在这样的环存在的情况下，“最短路径”的概念是没有意义的。虽然图6-13包含一个环{1，3，2}，但是边权值为正，所以Bellman-Ford和Dijkstra算法都能够适用。
图 6-16 Bellman-Ford详解例6-6：使用Bellman-Ford解单源最短路径
Bellman-Ford算法很直观地在图中推进n次，寻找是否存在一条边（u,v），能够在给定dist[u]和边（u,v）的权值下，更新dist[v]。我们需要至少n-1次推进，例如，在极端情况下，从源点s到某个顶点v的最短路径需要通过图中所有的顶点。另外，因为边可以以任意顺序访问，使用n-1次推进就能够确保所有的缩减路能够被发现。事实上，以不同的顺序访问边将会导致一个不同的计算dist值过程。图6-17所示的是在两个不同的图上执行Bellman-Ford算法，这两个图的区别在于标记为v4和v1的顶点。但是如果你考虑重标记的话，两个执行过程都能够得到同样的结果。
图 6-17 不同的Bellman-Ford执行过程，能够得到同样的结果如果存在负环，Bellman-Ford是不能正常工作的。为了检测负环，我们执行一个循环n次（不止一次），如果有调整dist的值，那么就存在负环。从嵌入的循环中可以很明显地看出来，Bellman-Ford的性能是O(V*E)。