本篇主要是證明一些單源最短路的性質。
開始說明性質之前，給出如下的定義：
, 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}))
且該等式之后保持不變。證畢。