1、Bellman-Ford 算法
它解决一般情况下的单源最短路径问题，允许边的权重为负值。同时对于给定的有向图G=（V, E)和权重函数w：E→R，它返回一个判断在路径中是否存在权重为负值的环路的布尔值。
Bellman_Ford(G, w, s) Initialize_Single_Source(G, s) for i = 1 to |G.V| - 1 for each edge(u, v)∈ G.E Relax(u, v, w) for each edge(u, v)∈G.E if v.d > u.d + w(u, v) return False return True这个算法易于理解：首先初始化，并设s.d = 0；之后我们一共循环|V|次，每次都会松弛从每个结点的出发的边，在最后我们判断每条边是否满足三角不等式性质。
引理2：设G = （V，E）为一个带权重的源节点为 s 的有向图，权重函数 w : E → R。假定图G中没有以源节点 s 出发可以到达的权重为负值的环路，那么算法 Bellman_Ford 算法在 2 ~ 4 的 for 循环执行了|V| - 1次后，对于所有从 s 到达的结点 v，我们有 v.d = δ(s, v)。
这个引理在书上的证明比较难懂，在此我用人话翻译一遍： 首先，我们考虑到每条路径中边的条数，在上次的文章中已经得到证明，最多的条数为|V| - 1，那么每第 i 次循环我们就只调整"该路径"的第 i 条边。
通俗的来讲，以第一循环为例：表面上我们松弛了所有的边，而实际上我们只专注于通往每个节点的简单路径上的第一条边，显然，这条边由源节点出发，即所有从源节点出发的边，这会让我们达到上述的目的：调整第 i 条边；而在第二次循环，我们将专注于每条简单路径上的第二条边，并依次类推。
由此，我们每次的循环的目的便是第 i 次循环我们就只调整"该路径"的第 i 条边。同时，根据路径松弛性质，由于它们是按路径上边的顺序进行松弛的，那么我们便可以得到 v. d = δ(s, v)的结论。
推论3：设G = （V，E）是一带权重的源节点为s的有向图，权重函数 w： E→R，假定图G中没有以源节点 s 出发可以到达的权重为负值的环路，则对于所有结点v∈V，存在从源节点s到v的路径当且仅当Bellman_Ford 算法终止时 v.d < ∞。
这个推论很显然啊，如果某节点不在一条可以由 s 到达的简单路径上， 那么无论我们怎么调整，其或者能够通向它的结点的d都为∞，无法通过Relax进行松弛的。
定理4：（Bellman_Ford 算法的正确性）设Bellman_Ford 算法运行在一条带权重的源节点为 s 的有向图G = （V， E）上，该图的权重函数 w: E→R。若图G不包含从s可以到达的权重为负值的环路，则算法返回TRUE，且对于所有v∈V，前驱子图Gp是一棵根节点为s的最短路径树，若G包含一条从s可以到达的权重为负值的环路，则算法返回False。
这个定理需要严密的论证：
证明：对于环路c = <V0, V1,……,Vk>，其中V0 = Vk，由其权值为负，得到：
，我们假设其返回True（反证法），那么根据返回true的条件，对于每一个结点，均有：
Vi.d ≤ Vi-1. d + w(Vi-1, Vi),那么把环路上所有结点的不等式加起来，有：
其中，和中，实际上环路中的每个点都出现且仅出现了一次，那么我们便可以消掉，从而得到的结果，然而这与假设相悖，从而其只能返回False。
2、有向无环图中的单源最短路径问题
在本节中，我们将根据结点的拓扑次序来对带权重的有向无环图G =（V，E）进行边的松弛操作。
（回忆：拓扑排序是根据对图的DFS调用来计算完成时间，并按结点的完成时间降序输出结点序列）
算法先对有向无环图进行拓扑排序，以确定一个线性次序。若有向无环图包含从结点 u 到 v 的一条路径，那么 u 在拓扑排序中从次序位于v的前方（u.f > v.f)，我们便按照其次序对所有结点进行处理。
DAG_Shortest_Path(G, w, s) topologically sort the vertices of G Initialize_Single_Source(G, s) for each vertex u, taken in topologically sorted order for each vertex v ∈ G.Adj[u] Relax(u, v, w)在该算法中需要注意的是，拓扑排序的第一个结点，即深度优先森林中的最后一个根节点可能并不是该问题中的源节点s，在拓扑排序中，它必然位于s的前方，即存在一条由其通往 s 的路径，因此同时又根据图中无环，因此 s 到达不了它，因此它的d值永远是∞，同样，可能也存在一些结点也在s的前方，因此s永远到达不了在拓扑排序位于它前方的结点。
定理5： 若带权重无环路的有向图G = （V， E）有一个源节点 s，则站在算法DAG_Shorteset_Path结束后，对于所有的结点 v ∈ V ，我们有 v.d = δ(s, v)，且前驱子图Gp是一棵最短路径树。
由于这个定理易于理解，我们就不看书上的证明了。在拓扑排序中，位于 s 前的结点，即 s 无法到达的结点，它们的d值都是∞，这一点我们已经论述过了，位于s 后的结点v，由于存在一条从 s 到 v 的路径 p = <V0, V1,……，Vk>，同时我们是按结点的顺序松弛其相邻的边的，同时我们对所有的边进行了松弛，那么松弛顺序必然符合路径上排列的顺序，因此根据路径松弛性质，在算法终止时，有 v.d = δ(s, v)。同时易得其前驱子图是一棵最短路径树。
