数据结构第19讲：第7章(4)最短距离,网络流

数据结构

7.8 最短路径问题1. 从某个源点到其余各点的最短路径 2. 每一对顶点之间的最短路径

数据结构

动态规划: 动态规划:C++语言描述 《数据结构,算法与应用—C++语言描述》 数据结构,算法与应用 C++语言描述》 汪诗林, Startaj Sahni 著,汪诗林,孙晓东 等译 机械工业出版社

与贪婪算法一样,在动态规划中, 与贪婪算法一样,在动态规划中,可将一个问题的 解决方案视为一系列决策的结果.不同的是, 解决方案视为一系列决策的结果.不同的是,在贪婪 算法中,每采用一次贪婪准则, 算法中,每采用一次贪婪准则 便做出一个不可撤回的 决策, 决策, 而在动态规划中, 而在动态规划中,还要考虑每个最优决策子序列为 最优.动态规划的基本思想是: 最优.动态规划的基本思想是: 最优序列由最优子序列构成. 最优序列由最优子序列构成. 或者,问题的最优解包含了子问题的最优解. 或者,问题的最优解包含了子问题的最优解. 2

数据结构

求从顶点1到顶点5的最短距离1 2 3 2 4 3 4 1 4 3 2 5 5

贪婪准则: 分步构造最短路径.每一步在路径中加入一 个顶点.假设当前已经到达顶点q,且不是目的 顶点5,则加入的下一个顶点贪婪策略为:选择 离q最近且目前不在路径中的顶点.1 1 3 4 4 5 2 5

10 63

数据结构

求从顶点1到顶点5的最短距离1 2 3 2 4 3 4 2 1 4 3 5 5

动态规划:按路径的长度递增的次序求各个最短距离子序列,并 保证子序列最优.最终得到总的最优序列(最优解). 路径长度为1:经过顶点1的从顶点1到顶点5的最短 距离(应取权值或∞ ),记为: c ( 1, 5, 1) = ∞4

数据结构

求从顶点1到顶点5的最短距离1 2 3 2 4 3 4 2 1 4 3 5 5

路径长度为2:经过顶点1和2的从顶点1到顶点5的最短 距离.由于顶点2的加入,最短距离值可能(动态)改变, 或者仍然为c ( 1, 5, 1);或者为从顶点1到顶点2的距离加 上从顶点2到顶点5的距离之和;记为: c ( 1, 5, 2) = min {c(1,5,1), c(1,2,1) + c(2,5,1) } = 95

数据结构

求从顶点1到顶点5的最短距离1 2 3 2 4 3 4 1 4 3 2 5 5

路径长度为3:经过顶点1,2和3的从顶点1到顶点5的 最短距离.由于顶点3的加入,最短距离值可能(动 态)改变,或者仍然为c ( 1, 5, 2);或者为从顶点1到 顶点3 (经过顶点1和2)的距离加上从顶点3到顶点5 (经 过顶点1和2)的距离之和;记为: c ( 1, 5, 3) = min {c(1,5,2), c(1,3,2) + c(3,5,2) } =96

数据结构

求从顶点1到顶点5的最短距离1 2 3 2 4 3 4 1 4 3 2 5 5

路径长度为4:经过顶点1,2,3和4的从顶点1到顶点5的 最短距离.由于顶点4的加入,最短距离值可能(动态) 改变,或者仍然为c ( 1, 5, 2);或者为从顶点1到顶点3 (经过顶点1,2和3)的距离加上从顶点3到顶点5 (经过顶点 1,2和3)的距离之和;记为: c ( 1, 5, 4) = min {c(1,5,3), c(1,4,3) + c(4,5,3) } = 6 最后得到一个决策子序列: 最后得到一个决策子序列: c(

1,5,1),c(1,5,2),c(1,5,3),c(1,5,4) 7

数据结构

算法归纳: 算法归纳: 设图的顶点编号为1 设图的顶点编号为1到n,令c(i,j,k)表 c(i,j, 示从顶点i出发,经过编号为{1, ,k}的顶 {1,…,k} 示从顶点i出发,经过编号为{1, ,k}的顶 点到顶点j 点到顶点j的最短距离.且: c(i,j,k ) = min {c(i,j,k-1), c(i,k,k-1) + c(k,j,k-1)} 当k=n时,c(i,j,k)为顶点i到顶点j的最短距离. 如何计算 c( i, j, n ) ? 1. 递归:终止条件为: c(i, j, 1 ) = A [ i, j ]; 2. 迭代:初始条件为 c(i, j, 1 ) = A [ i, j ];

//邻接矩阵表示 邻接矩阵表示 //邻接矩阵表示 邻接矩阵表示8

数据结构

递归算法: 递归算法:int C_i_j( int i, int j, int& k) { //求顶点 到j的最短距离,k的初始值为 图以邻接矩阵表示 求顶点i到 的最短距离 的最短距离, 的初始值为 的初始值为n, 求顶点 if ( k==1) return A[i, j]; c_ik = C_i_j( i, k, k-1) ; c_kj = C_i_j( k, j, k-1) ; c_ij = C_i_j( i, j, k-1) ; if(c_ik+c_kj) < c_ij ) return c_ik +c_kj; return c_ij ; 时间复杂度: 时间复杂度: } T(k)=3T(kT(k)=3T(k-1) + C T(n)= O(3n)9

数据结构

递归过程中有大量的重复计算. 递归过程中有大量的重复计算.(1, n, k)

( 1, k, k-1)

(k, n, k-1)

( 1,n, k-1)

(1,k-1,k-2)

(1, k, k-2)

(k,k-1,k-2)

(k, n, k-2)

(1,k-1,k-2)

( 1,n, k-2)

(k-1,k,k-2)

(k-1,n,k-2)

(k-1,n,k-2)

采用迭代方法,从初始状态开始, 采用迭代方法,从初始状态开始,每次记录中间 结果,可以减少重复.时间复杂度O( 结果,可以减少重复.时间复杂度 (n3).10

数据结构

2. 求每一对顶点之间的最短路径有两种方法: 分别以图中的每个顶点为源点, 共需要n次调用迪杰斯特拉算法,时间复杂度为O( n3) ;

另一种方法是弗洛伊德算法,时间复杂度也是O( n3) ,但算法更简单;11

数据结构

弗洛伊德算法的基本思想:从图的带权邻接矩阵G.arcs出发, 假设求顶点Vi到Vj的最短路径.如果从Vi,到 Vj有弧,则从Vi,到Vj存在一条长度为G.arcs[i][j] 的路径,但该路径是否一定是最短路径,还需 要进行n次试探.

数据结构

1.第一次,判别( Vi, V1 )和(V1,Vj ), 即判别(Vi, V1 , Vj)是否存在,若存在,则比较 ( Vi, Vj )和(Vi, V1 , Vj)的长度,取长度较短 者为从Vi到Vj中间顶点序号不大于1的最短路径.v1 vi

vjj=1,2,…, n; = ;

对所有的点对之间, 对所有的点对之间,即: i=1,2,…, n ; =

共执行 n2 次.

数据结构

2. 第二次,再加一个顶点V2,如果(Vi, … , V2) 和 (V2, … , Vj)分别是当前找到的中间顶点序号不大于1 的最短路径,那么(Vi, … , V2, … , Vj )就有可能是从 Vi,到Vj的中间顶点序号不大于2的路径.将它和已经 得到的从Vi,到Vj中间顶点序号不大于1的最短路径相 比较,取较短者为从Vi到Vj的中间顶点序号不大于2 的路径. v1

共执行 n2 次

vi v2

vj

3. 第三次,再加一个顶点V3,继续进行试探.14

数据结构

6 V3 3 9 V1 V0 V2 1 7 8 4 5 4 2 V4(0) A(1) =

1 0 0 8 3 0 8

2 1 0 5 4 1 8

3 2 9 0 6 8

4

4 2 8 7 0 1 2 3 4

A(0)为有向网的邻接矩阵 第一步:以A(0)为基础,以V1为中间顶点,求从 Vi到Vj的最短路径.该路径或者为从Vi到Vj的边, 或者为(Vi,V1)+(V1,Vj) . A(1) [i][j] = min{A(0) [i][j], A(0) [i][1]+A(0) [1][j]}15

数据结构

6 V3 10 3 9 V1 V0 V2 V1 1 6 7 3 4 4 2 V4(2) (1) = A(-1)=

1 0 0 8 3 0 8

2 1 0 5 4 1 8

3 8 9 0 6

4 1 2 3 4 2 6 8 7 0

2 3 10 4

以A(1)为基础,以V2为中间顶点,求从Vi,到Vj 的最短路径.该路径或者为从Vi到Vj的边, 或者 为从Vi开始通过V2或V1到达Vj的最短路径 . A(2) [i][j] = min{A(1) [i][j], A(1) [i][2]+A(1) [2][j]}16