本节就之前给出的一部分性质进行严密的证明，而非通过“显然”等模糊的语句。
1、三角不等式性质
引理10：设G = （ V，E）为一个带权重的有向图，其权重函数 w :E→R，其源节点为s。那么对于所有边(u, v)∈E，我们有：
δ(s, v) ≤ δ(s, u) + w(u, v)
证明：假定 p 是从 s 到结点 v 的一条最短路径，则 p 的权重不会比任何从s 到 v 的其他路径的权重大，不过我们在此处特指了由s到u再到v的一条路径。
2、最短路径估计值的松弛效果
引理11：（上界性质）设G = （V，E）为一个带权重的有向图，权重函数 w : E→R，其源节点为s，并由Initialize_Single_Source(G, s)初始化，那么对于所有结点 v ∈V，v.d ≥ δ(s, v)，并且该不等式在对图的边进行任何次序的松弛过程中保持成立，且：v.d取得下界δ(s, v)时，将不再发生变化。
证明：我们使用归纳法。
1、基础步骤：在初始化后，对所有结点 v ∈ V，v.d ≥ δ（s, v)显然成立。因为 v.d = ∞ 意味着所有的结点 v ∈V - {s}，v.d ≥ δ(s, v)，对于源节点，我们单独考虑：若 s 在一个权重为负值的环路上，那么δ(s, s) = -∞，否则为0.这一位置 s. d = 0 ≥ δ(s, s)必然成立。
2、归纳步骤： 考虑对边(u, v)的松弛操作。根据归纳假设，在松弛前，对所有 x ∈ V，我们有x.d ≥ δ(s, v)。而在对边(u, v)进行松弛操作的过程中，唯一可能发生改变的d值仅有v.d，如果该值发生改变，有：
v. d = u. d + w(u, v) ≥ δ(s, u) + w(u ,v) ≥ δ(s, v)（三角不等式）即得到维持。
3、最终，在v. d = δ(s, v)时，注意它达到其取值的下界后， v.d 无法减小，因为刚刚证明了 v.d ≥ δ(s, v)——而松弛操作是对当发现一条权值相对较少的路径时，才将其更替为v.d。即松弛操作不增加d值——因此将不会发生变化。
3、推论12（非路径性质）：给定一个带权重的有向图G=（V，E），权重函数为 w：E→R，假定从源节点 s ∈V 到给定结点 v ∈ V 之间不存在路径，则在该图由Initialize_Single_Source(G, s)算法进行初始化后，我们有 v.d = δ（s, v) = ∞，并且该等式作为不变式一直维持到图G所有松弛操作结束。
证明：根据上界性质，我们总有v.d ≥ δ(s, v) = ∞（注意，此处δ(s, v) = ∞ 为已知量。）因此 v.d = δ(s, v) = ∞。
4、引理13：设G = （V，E）为一个带权重的有向图，权重函数w：E→R，且边（u, v)∈E，那么在对边(u, v)进行Relax(u, v, w)后，有v.d ≤ u.d + w(u, v)。
证明：若在松弛前，我们有 v.d > u.d + w(u, v)，那么在松弛后， v. d = u.d + w(u, v)。
同时，若在松弛后，我们有v. d ≤ u. d + w(u, v)，那么松弛后，其值仍然不会发生改变。
5、引理14（收敛性质） 设G = （V，E）为一个带权重的有向图，权重函数 w：E→ R。设 s ∈V为某个源节点，s -> u→v为图中的一条最短路径，其中u, v∈V。假定图G由Initialize_Single_Source(G, s)初始化，并在其之后进行了一系列的松弛操作，其中包括对边(u, v)的松弛操作Relax(u, v, w)，若在松弛前有u. d = δ(s, u)，那么在松弛后，v.d = δ(s, v)。
证明：根据上界性质，u.d = δ(s, u)将不会发生变化。同时，在松弛边(u, v)时，发生：
v. d ≤ u. d + w(u, v) = δ(s, u) + w(u, v) = δ(s, v)（最短路径的最优子结构），同时再根据上界性质，其也会保持不变。
6、引理15（路径松弛性质）：设G = （V，E）为一个带权重的有向图，权重函数w：E→R，设 s ∈ V 为某个源节点，考虑从 s 到Vk 的一条最短路径p = <V0, V1,……, Vk>，若图由Initialize_Single_Source(G, s)初始化，并进行了一系列的松弛操作，其中按顺序对边(V0, V1), (V1, V2),……, (Vk-1, Vk)，那么在进行了这些松弛操作后，我们有 Vk. d = δ(s, Vk)，并一直保持不变，该性质与对其他边的松弛操作无关。
证明：根据最优子结构和上界性质进行证明：书上还用到了归纳假设法：假设最短路径p在第i条边被松弛之后，有Vi.d = δ(s, Vi)。
则在基础步：i = 0时，显然 V0. d = s. d = δ(s, s) = 0 假设成立，同时s.d将在这之后不会发生变化。
在归纳步：根据最短路径的最优子结构，从在V0到Vi的最短路径上，V0到Vi-1也是一条最短路径。同时我们已经有Vi-1.d =δ(s, Vi-1)，同时根据收敛性质，在对边(Vi-1, Vi)进行松弛后，我们有Vi.d = δ(s, Vi)，并在这之后不会发生变化。即得到证明。
松弛操作和最短路径树
引理16：设G=（V，E）为一个带权重的有向图，权重函数 w：E→R，设 s ∈V为某个源节点，假定G不包含从源节点s可以到达的权重为负值的环路，则在图G由Initialize_Single_Source(G, s)算法初始化之后，前驱子图Gp形成根节点为源节点s的有根树，并且任何对图G的边的任意松弛操作将维持该性质不变。
证明：在初始化时，Gp中的唯一结点为 s。引理显然成立。现在考虑经过一系列松弛操作后的前驱子图Gp。
笔者注：以下关于无环路的证明与书上给出的方法不同，是因为我觉得书上的方法不太严谨——它相加了状态不统一的结点的d值，并相消掉。（即对边松弛前后）
首先，先证明Gp无环路：假定在松弛序列的某个步骤上在图Gp创建了一个环路 c =<V0, V1, ……, Vk>，其中有V0 = Vk，那么Vi.p = Vi-1。同时，假定在对边(Vk-1, Vk)进行松弛操作时创建了该环路。
在这之前，我们需要得知：所有环路上的结点都能从源节点s到达。——在进入环路时，必然V0需要一个前驱结点来到达，从而便能到达整个环路。根据这个信息，我们有结论：Vi.d ＜ ∞。
之后，我们试图证明c是一个权重为负值的环路，从而说明环路本身不存在。
在松弛边(Vk-1, Vk)之前，除了Vk-1和Vk，在环路上的其他结点，我们均有：Vi.p = Vi-1。因此，我们考虑对它们的松弛操作——在对它们进行松弛操作的时候，才会发生p的修改，而此时同时发生的还有对Vi.d的修改，并使得它：
Vi.d = Vi-1. d + w(Vi-1, Vi)。同时，在对这条边进行松弛操作前，我们有：Vi.d > Vi-1.d + w(Vi-1, Vi)。
同样的，在松弛最后一条边(Vk-1, Vk)前，我们也有：Vk.d > Vk-1.d +w(Vk-1, Vk)。然而，我们考虑在松弛边(Vk-1, Vk)前，从Vk以V0的身份依次经过V1、……最后到达Vk-1的路径：在之前，由于我们更新了除V0外每个结点的p值，这表明在更新后，我们有：Vk-1.d =Vk-2.d + w(Vk-2, Vk-1)= Vk-3.d+w(Vk-3, Vk-2) + w(Vk-2, Vk - 1) = V0.d +w(V0, V1) + w(V1, V2) + …… + w(Vk-2, Vk - 1)
在松弛最后一条边(Vk-1, Vk)时，我们有 Vk.d > Vk-1.d + w(Vk-1, Vk)。带入上式，有：
Vk.d > V0.d + w(V0, V1) + w(V1, V2) + ……+ w(Vk-1, Vk)。
其中，Vk.d和V0.d在对边（Vk, Vk-1)进行松弛前相等——因为仅在对边(u, v)进行松弛时它才发生改变。同时，消去该值后，我们右边所得的便是整个环路的总权重——得到的结果为负值。因此得出矛盾，即环路不存在。
现在我们拥有了图Gp是一个有向无环图的结论。为证明其形成一棵根节点为s的有根树，只需证明对 v ∈Vp，在Gp中存在一条从源节点s到达v的简答路径路径。
证明如下：由于Vp中仅包含具有非空p值的结点，因此，再加上结点s，同时，在图Gp中，边Ep中仅包含(v.p, v)——即表示它是由结点的p属性诱导的边的集合。因而从源节点发出的边递归，我们便得到一个能包含所有具有非空p值的点的图。然而，我们可以看到，它仅证明了简单路径的存在，并未证明唯一性。现在又需证明其唯一性：
若在图Gp中，从源节点s到达某个节点v具有两条简单路径，那么这两条路径上必然会在最后回归到一条路径上（当然，也可能是直接回归到结点v），我们假设回归的这个结点为u，那么我们会显然的发现bug：u同时具有两个u.p属性——这明显是不可能的。在松弛操作中，必然会比较这两个u.p的d属性，并选择其中一个作为u结点唯一的p属性，并因此得到证明。
有了这么多基础，我们终于可以回到最初我们想要证明的东西：在执行了一系列的松弛操作后，所有结点都取得了其最后的最短路径权重，则Gp为一棵最短路径树。
引理17：（前驱子图性质）设G = （V，E）为一个带权重的有向图，权重函数 w ：E→R，设s∈V为源节点，假定图G不包含从s可以到达的权重为负值的环路。假定调用Initialize_Single_Source(G, s)对图进行初始化，然而对图G的边进行任意次序的松弛操作。该松弛操作序列将针对所有结点v∈V生成的v.d = δ(s, v)，则前驱子图Gp形成一棵根节点为s的最短路径树。
证明：我们先回到最短路径树的定义：
一棵根节点为s的最短路径树是一个有向子图G' = (V', E')，其中V' ∈ V，E' ∈ E，满足：
1、V' 是图G中从源节点 s 可以到达的所有结点的集合。
2、G' 形成一棵根节点为 s 的树。
3、对于所有结点 v ∈ V'，图G’中从结点 s 到结点 v 的唯一简单路径是图G中从结点 s 到结点 v的一条最短路径。
对性质1：在上述中，我们已经得知了在集合Vp中的结点的d 是有限值，且它们可被到达。而根据上界定理，δ(s, v) ≤ v.d，因此δ(s, v)有限，从而我们得到它是可从源节点s到达的。
对性质2：可直接由引理16导出。
对性质3：对结点v来说，其属性p和d是相关联——p的选择为其相对较短路径上的前驱结点，而若考虑对所有边进行松弛，那么会选择比较所有路径上的最短路径的前驱结点，即得到证明。
（注：详细的证明见书394页）
