距離函數，我們說壹個距離函數是有效的當且僅當有效函數被滿足。
(1)d(t)= 0；
(2)d(I)& lt；= d(j)+1(如果弧rij在剩余網絡G(x)中)；
房產1:
如果距離標簽有效，則d(i)是剩余網絡中從點I到匯點的距離的下限；
證明:
設從節點I到交匯點T的任意壹條長度為k的路徑為I = i1-I2-i3...ik+1 = T。
d(I(k))& lt；= d(I(k+1))+1 = d(t)+1 = 1
d(I(k-1))& lt；= d(I(k))1 = 2
d(I(k-2))& lt；= d(i(k-1))+1=3
：
：
d(I(1))& lt；= d(I(2))1 = k
因此，d(i)是從I到t的距離的下限。
屬性2:
允許弧(邊):如果為邊Rij >；0，且d(i)= d(j)+1，則稱之為允許邊。
允許路徑:從源點到匯點的路徑，由允許的弧組成。
允許路徑是從源點到匯點的最短增廣路徑。
證明:
(1)因為rij >；所以壹定是增開的路。
(2)假設路徑P是包含k條弧的容許路徑，由d(i) = d(j)+1可知d(s)= k；
又因為d(s)是S點到交匯點距離的下限，所以距離的下限是K，所以P是最短路徑。
屬性3:
距離標簽在sap算法中總是正確有效的。而且每打壹次標簽，距離標簽都會嚴格增加。
證明:省略；
偽代碼:
//算法最短增廣路徑；
無效sap()
{
x = 0；
獲得精確的距離標簽d(I)；
I = s；
while(d(s)& lt；n)
{
if (i有壹個可接受的弧)
{
預付款(壹)；
如果(i == t)
{
增強；
I = s；
}
}
其他
靜修(壹)；
}
}
//過程推進(I)；
無效預付款(壹)
{
設(I，j)是A(t)中的容許弧；
pre(j)= I；
I = j；
}
//程序撤退
無效撤退()
{
d(I)= min(d(j)+1):rij & gt；0;
如果(我！= s)
I = pre(I)；
}
代碼模板:
# include & ltiostream & gt
# include & ltcstring & gt
# include & ltcstdlib & gt
using命名空間std
constint Max = 225
consint oo = 210000000；
int n，m，c[Max][Max]，r[Max][Max]，c1[Max][Max]，source，sink
//c1是c的反向網絡，用來初始化dis數組。
int dis[Max]；
Void initialize()//初始化dis數組。
{
int q[Max]，head =0，tail = 0；//BFS隊列
memset(dis，0，sizeof(dis))；
q[++ head]= sink；
while(tail & lt；頭)
{
int u = q[++tail]，v；
for(v = 0；v & lt=水槽；v++)
{
如果(！dis[v]& amp；& ampc 1[u][v]& gt；0)
{
dis[v]= dis[u]+1；
q[++ head]= v；
}
}
}
}
int maxflow_sap()
{
initialize()；
int top = source，pre[Max]，flow =0，I，j，k，low[Max]；
// top是當前增廣道路中的前方點。
memset(low，0，sizeof(low))；//低數組//用於存儲路徑中的最小容量。
while(dis[source]& lt；n)
{
bool flag = false
低[源]= oo；
for(I = 0；我& lt=水槽；I++)//根據允許弧的定義，找到允許弧。
{
if(r[top][I]& gt；0 & amp& ampdis[top] == dis[i] +1)
{
flag = true
打破；
}
}
If(flag)//如果找到允許的弧，
{
low[I]= r[top][I]；
if(low[I]& gt；low[top])low[I]= low[top]；//更新低電平
pre[I]= top；top = I；
If(top == sink)//如果找到壹條增廣路徑，
{
flow+= low[sink]；
j =頂部；
而(j！= source)//路徑回溯更新剩余網絡。
{
k = pre[j]；
r[k][j] -=低[匯]；
r[j][k] +=低[匯]；
j = k；
}
top = source//從頭開始尋找最短路徑。
memset(low，0，sizeof(low))；
}
}
Else//如果不允許弧
{
int mindis = 10000000；
for(j = 0；j & lt=水槽；J++)//找到與top相鄰的dis最小的點。
{
if(r[top][j]& gt；0 & amp& ampmindis & gtdis[j] +1)
mindis = dis[j]+1；
}
dis[top]= mindis；//更新top的距離值。
如果(頂！= source)top = pre[top]；//回去另想辦法
}
}
回報(流量)；
}