本篇主要是證明一些單源最短路的性質(zhì)。
開(kāi)始說(shuō)明性質(zhì)之前，給出如下的定義：
, v \in G)
表示源s到v的最短距離，也是最短路解的結(jié)果。
,v=1,\dots,n)
表示在求解過(guò)程中對(duì)
)
的估計(jì)。
,v \in V)
表示節(jié)點(diǎn)v在最短路中的前驅(qū)。
)
做如下操作：
=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})
下面若無(wú)特殊說(shuō)明，則默認(rèn)以下條件：
)
是一個(gè)有向帶權(quán)圖，源為s，權(quán)函數(shù)
(Property Triangle inequality)對(duì)所有的邊
\in E)
有
 \leq \delta(s,u) + w(u,v))
。
Proof 是源s到v的最短距離，那么它當(dāng)然小于這么一條特殊的路線：從s出發(fā)走最短路到u(此時(shí)距離為
)
)接著直接由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 用數(shù)學(xué)歸納法對(duì)relax操作步數(shù)進(jìn)行歸納證明。當(dāng)初始化后，
 =0 \geq \delta(s,s))
(若s處于一個(gè)帶負(fù)權(quán)的環(huán)中，則
=-\infty)
;否則
=0)
)。而
 = +\infty \geq \delta(s,v), \any v \in V-\{s\})
。
現(xiàn)在看第k步Relax操作，在此之前，由歸納假設(shè)有
 \geq \delta(s,u), \any u\in V)
。不失一般性，假設(shè)第k步Relax是對(duì)邊(u,v)進(jìn)行操作，若
 \leq d(u)+w(u,v))
，則
)
不變，由歸納假設(shè)有，
 \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))
每次對(duì)邊(u,v)進(jìn)行Relaxation操作時(shí)，
只會(huì)減少，當(dāng)
減到
時(shí)，它無(wú)法再減少了，但它也無(wú)法增加，所以
就保持
不變。
(No-path Property)若源s無(wú)法到達(dá)點(diǎn)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)假設(shè)路徑從s到u再直接到v是一條最短路，若在Relax(u,v)之前的任何時(shí)刻，只要
=\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))
。第一個(gè)不等號(hào)用到引理1，第一個(gè)等號(hào)用到定理的假設(shè)，第二個(gè)等號(hào)用到最短路的最優(yōu)子結(jié)構(gòu)：最短路的子路徑也是最短路，
+w(u,v)\geq \delta(s,v))
而
+w(u,v))
不可能大于
，否則
-w(u,v)<\delta(s,u))
違反了
是s到u的最短距離的假設(shè)。
再由Upper-Bound Property有
\geq\delta(s,v))
。由上面兩式有
。證畢。
(Path-relaxation Property)設(shè)
是一條最短路。若ININITIALIZE-SINGLE-SOURCE(G,s)后有一系列的Relax操作，依次作用在邊
,\dots,(v_{k-1},v_{k}))
上，則最后有
=\delta(s,v_{k}))
且之后都不變。這些Relax操作之間可以加入任何其它的Relax操作，包括Relax該最短路上的邊。
Proof 用數(shù)學(xué)歸納法對(duì)Relax邊的次序進(jìn)行歸納。首先INITIALIZE-SINGLE-SOURCE(G,s)后，有
=\delta(s,s)=0)
。設(shè)第i-1條邊被Relax后有
=\delta(s,v_{i-1}))
。由Upper-Bound Property知這個(gè)等式之后都保持不變。特別的在
)
時(shí)有
，由Convergence Property知Relax操作后有
=\delta(s,v_{i}))
且該等式之后保持不變。證畢。