二、实验原理
1.求赋权图G=（V，E，F）中任意两点间的最短路的Floy d算法.
设A=（aij）n×n为赋权图G=（V，E，F）的矩阵，当vivj∈E时aij=F（vivj），否则取aij=0，aij=+∞（i≠j），dij表示从vi到vj的距离，rij表示从vi到vj的最短路中一个点的编号.
①赋初值.对所有i，j，dij=aij，rij=j，k=1.转向②.
②更新dij，rij.对所有i，j，若
，则令dij=dik+dkj，rij=k，转向③.
③终止判断.若dij＜0，则存在一条含有顶点vi的负回路，终止；或者k=n终止；否则令k=k+1，转向②.
最短路线可由rij得到.
2.求最小生成树的Pri m算法.
假设N=（V，{E}）是一个连通图，U是顶点集V的一个非空子集.若（u，v）是一条具有最小权值的边，其中u包含于U，v包含于V-U，则必存在一棵包含边（u，v）的最小生成树.
算法描述：从U={u0|u0∈V}，S=φ开始，重复执行下述步骤：
在所有u属于U，v属于V-U的边（u，v）属于E中找一条代价最小的边（u0，v0）并入集合S，同时v0并入U，直到U=V为止，此时S中必有n-1条边，则T=（V，{E}）为N的最小生成树.
3.从一个可行流f开始，求最大流的Ford--Fulkerson标号算法的基本步骤.
（1）标号过程.
Step1：给发点vs以标号（+，+∞），δs=+∞.
Step2：选择一个已标号的点x，对于x的所有未给标号的邻接点y，按下列规则处理：
当yx∈E，且fyx＞0时，令δy=min{fyx，δx}，并给y以标号（x-，δy）.
当xy∈E，且fxy＜Cyx时，令δy=min{Cxy-fxy，δx}，并给y以标号（x+，δy）.
Step3：重复Step2直到收点vt被标号或不再有点可标号为止.若vt得到标号，说明存在一条可增广链，转（2）调整过程；若vt未得到标号，标号过程已无法进行时，说明f已经是最大流.
（2）调整过程.
Step4：决定调整量δ=δvt，令u=vt.
Step5：若u点标号为（v+，δu），则以fvu+δ代替fvu；若u点标号为（v-，δu），则以fvu-δ代替fvu.
Step6：若v=vs，则去掉所有标号转（1）重新标号；否则令u=v，转Step5.
算法终止后，令已有标号的点集为S，则割集（S，Sc）为最小割，从而Wf=C（S，Sc）.