第四节 最短路问题及算法
• 定义6.11 (1)若H 是赋权图G 的一个子图,则称H 各边的
权和 W H eEH为W He的权。类似地,若P(u,v)是赋权图G 中从u
到v 的路,称
W P 为路W Pe 的权。 eE P
(2)在赋权图G 中,从顶点u 到顶点v 具有最小权的路
P * (u,v),称为u 到v 的最短路。
第二节 路径、回路与连通性
例1 图6-6中所给出的从结点1出发而终止于结点3的一
些路是：
L1={1,3};
L2={1,4,3};
L3={1,2,3};
L4={1,2,4,1,4,3};
L5={1,1,1,4,3}。
图6-6所给出的部分回路是:
C1={1,2,1};
C2={1,2,4,1};
C4={1,2,1,2,4,1}; C5={1,4,1,2,4,1}.
图6-14 修改2 、3标号
P(3)=3 T(5)=+ ∞
图6-15 改P(3)=3
第四节 最短路问题及算法
• 解 第3步:修改与3相连的T标号
T(5)=min{T(5),P(3)+d(3,5)}=6;在所有剩下的
T标号中2的标号最小,改为P(2)=4,如图6-16所示;
第4步:修改与2相连的T标号 T(4)=min{T(4),P(2)+d(2,4)}=7,T(5)=min{T(5),P(2)+d(
第五节 网络最大流问题
图6-30 第四次标号
图6-31 第四次调整
第五节 网络最大流问题
•
图6-32 最终标号
的标号为P(3)=3,如图6-15所示;
T(2)=+ ∞ T(4)=+ ∞
