本篇主要是证明一些单源最短路的性质。
开始说明性质之前，给出如下的定义：
, v \in G)
表示源s到v的最短距离，也是最短路解的结果。
,v=1,\dots,n)
表示在求解过程中对
)
的估计。
,v \in V)
表示节点v在最短路中的前驱。
)
做如下操作：
=0,\delta(s,v)=\inf, v \in V\\\{s\},\pi(v)=NIL)
)
做如下操作：
若
 \geq d(v_{i})+w(v_{i},v_{j}))
则
 = d(v_{i})+w(v_{i},v_{j}); \pi(v_{j})=v_{i})
下面若无特殊说明，则默认以下条件：
)
是一个有向带权图，源为s，权函数
(Property Triangle inequality)对所有的边
\in E)
有
 \leq \delta(s,u) + w(u,v))
。
Proof 是源s到v的最短距离，那么它当然小于这么一条特殊的路线：从s出发走最短路到u(此时距离为
)
)接着直接由u到v(再加上距离
)
)，证毕。
(Upper-Bound Property)INITIALIZE-SINGLE-SOURCE(G,s)后，有不等式
 \geq \delta(s,v), \any v \in V)
成立，且该不等式在往后的任何顺序的松驰(Relaxation)操作都保持不变。一旦
=\delta(s,v),v \in V)
则d(v)就保持不变。
Proof 用数学归纳法对relax操作步数进行归纳证明。当初始化后，
 =0 \geq \delta(s,s))
(若s处于一个带负权的环中，则
=-\infty)
;否则
=0)
)。而
 = +\infty \geq \delta(s,v), \any v \in V-\{s\})
。
现在看第k步Relax操作，在此之前，由归纳假设有
 \geq \delta(s,u), \any u\in V)
。不失一般性，假设第k步Relax是对边(u,v)进行操作，若
 \leq d(u)+w(u,v))
，则
)
不变，由归纳假设有，
 \geq\delta(s,v))
；若，
 \geq d(u)+w(u,v))
，则Relax之后有不等式
=d(u)+w(u,v)\geq\delta(s,u)+w(u,v)\geq\delta(s,v))
每次对边(u,v)进行Relaxation操作时，
只会减少，当
减到
时，它无法再减少了，但它也无法增加，所以
就保持
不变。
(No-path Property)若源s无法到达点v，则
=\delta(s,v)=+\infty)
总成立。
Proof 由上面的Upper-Bound Property知，
 \geq \delta(s,v) = +\infty)
，所以
。证毕。
引理1：在Relax(u,v)完后立即有
\leq d(u)+w(u,v))
Proof 若
，引理成立；若
>d(u)+w(u,v))
，则Relax(u,v)后，有
<d(u)+w(u,v))
(Convergence Property)假设路径从s到u再直接到v是一条最短路，若在Relax(u,v)之前的任何时刻，只要
=\delta(s,u))
则Relax(u,v)之后有
=\delta(s,v))
Proof 由条件知在Relax(u,v)之前有
，则Relax(u,v)之后，有
\leq d(u)+w(u,v)=\delta(s,u)+w(u,v)=\delta(s,v))
。第一个不等号用到引理1，第一个等号用到定理的假设，第二个等号用到最短路的最优子结构：最短路的子路径也是最短路，
+w(u,v)\geq \delta(s,v))
而
+w(u,v))
不可能大于
，否则
-w(u,v)<\delta(s,u))
违反了
是s到u的最短距离的假设。
再由Upper-Bound Property有
\geq\delta(s,v))
。由上面两式有
。证毕。
(Path-relaxation Property)设
是一条最短路。若ININITIALIZE-SINGLE-SOURCE(G,s)后有一系列的Relax操作，依次作用在边
,\dots,(v_{k-1},v_{k}))
上，则最后有
=\delta(s,v_{k}))
且之后都不变。这些Relax操作之间可以加入任何其它的Relax操作，包括Relax该最短路上的边。
Proof 用数学归纳法对Relax边的次序进行归纳。首先INITIALIZE-SINGLE-SOURCE(G,s)后，有
=\delta(s,s)=0)
。设第i-1条边被Relax后有
=\delta(s,v_{i-1}))
。由Upper-Bound Property知这个等式之后都保持不变。特别的在
)
时有
，由Convergence Property知Relax操作后有
=\delta(s,v_{i}))
且该等式之后保持不变。证毕。