bon

本篇主要是證明一些單源最短路的性質。

開始說明性質之前，給出如下的定義：
表示源s到v的最短距離，也是最短路解的結果。
表示在求解過程中對的估計。
表示節點v在最短路中的前驅。

做如下操作：


做如下操作：
若則

下面若無特殊說明，則默認以下條件：
是一個有向帶權圖，源為s，權函數

(Property Triangle inequality)對所有的邊有。

Proof
  是源s到v的最短距離，那么它當然小于這么一條特殊的路線：從s出發走最短路到u(此時距離為)接著直接由u到v(再加上距離)，證畢。


(Upper-Bound Property)INITIALIZE-SINGLE-SOURCE(G,s)后，有不等式成立，且該不等式在往后的任何順序的松馳(Relaxation)操作都保持不變。一旦則d(v)就保持不變。

Proof
    用數學歸納法對relax操作步數進行歸納證明。當初始化后，(若s處于一個帶負權的環中，則;否則)。而。
    現在看第k步Relax操作，在此之前，由歸納假設有。不失一般性，假設第k步Relax是對邊(u,v)進行操作，若，則不變，由歸納假設有，；若，，則Relax之后有不等式
    
每次對邊(u,v)進行Relaxation操作時，只會減少，當減到時，它無法再減少了，但它也無法增加，所以就保持不變。


(No-path Property)若源s無法到達點v，則 總成立。

Proof
    由上面的Upper-Bound Property知，，所以。證畢。



引理1：在Relax(u,v)完后立即有

Proof    若，引理成立；若，則Relax(u,v)后，有



(Convergence Property)假設路徑從s到u再直接到v是一條最短路，若在Relax(u,v)之前的任何時刻，只要則Relax(u,v)之后有

Proof    由條件知在Relax(u,v)之前有，則Relax(u,v)之后，有。第一個不等號用到引理1，第一個等號用到定理的假設，第二個等號用到最短路的最優子結構：最短路的子路徑也是最短路，而不可能大于，否則違反了是s到u的最短距離的假設。
再由Upper-Bound Property有。由上面兩式有。證畢。



(Path-relaxation Property)設是一條最短路。若ININITIALIZE-SINGLE-SOURCE(G,s)后有一系列的Relax操作，依次作用在邊上，則最后有且之后都不變。這些Relax操作之間可以加入任何其它的Relax操作，包括Relax該最短路上的邊。

Proof    用數學歸納法對Relax邊的次序進行歸納。首先INITIALIZE-SINGLE-SOURCE(G,s)后，有。設第i-1條邊被Relax后有。由Upper-Bound Property知這個等式之后都保持不變。特別的在時有，由Convergence Property知Relax操作后有且該等式之后保持不變。證畢。