算法与数据结构

1

第十九讲最短路径12教材与参考资料普通高等教育“十一五”国家级规划教材普通高等教育精品教材《算法与数据结构—C语言描述》（第2版）张乃孝编著,高等教育出版社2008.第9章图（9.5）普通高等教育“十一五”国家级规划教材配套参考书《算法与数据结构》（第2版）学习指导与习题解析张乃孝编著,高等教育出版社2009.239.5最短路径如果图中从一个顶点可以到达另一个顶点，则称这两个顶点间存在一条路径。从一个顶点到另一个顶点间可能存在多条路径，而每条路径上经过的边数并不一定相同。如果图是一个带权图，则路径长度为路径上各边的权值的总和，两个顶点间路径长度最短的那条路径称为两个顶点间的最短路径，其路径长度称为最短路径长度。49.5.1Dijkstra算法Dijkstra算法求解从顶点v0出发到其它各顶点最短路径。该算法假设所有边的权都大于等于零。5基本思想设置一个集合U，存放已求出最短路径的顶点，V-U是尚未确定最短路径的顶点集合。U的初始状态为{v0}。按路径长度递增的次序逐个产生vx的最短路径,把vx加入U中。直到U=V时终止。距离值V-U图GUv0vi1vi3vi2为每个顶点设置一个距离值（已知最短距离）：集合U中某顶点的距离值就是从顶点v0到该顶点的最短路径长度；集合V-U中某顶点的距离值是从顶点v0到该顶点的只包括集合U中顶点为中间顶点的最短路径长度。性质：若vi是V-U中距离值最小的结点，那么这个距离值就是从v0到vi的最短路径。。67初始状态：集合U中只有顶点v0，顶点v0对应的距离值为0，集合V-U中顶点vi的距离值为边(v0,vi)(i=1,2,…,n-1)的权，如果v0和vi间无边直接相连，则vi的距离值为∞（实际程序中可以用一个足够大的数代替）。处理框架：（1）在集合V-U中选择距离值最小的顶点vmin加入集合U；（2）对集合V-U中各顶点的距离值进行修正：如果加入顶点vmin为中间顶点后，使v0到vi的距离值比原来的距离值更小，则修改vi的距离值。（3）重复（1）（2）操作，直到从v0出发可以到达的所有顶点都在集合U中为止。按路径长度递增的次序逐个产生最短路径例：已知带权图G10如下图所示及其邻接矩阵A，求从顶点v0到其它各顶点的最短路径úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥=03030350201502051504510500A45v050v15v41520v215v33v53520301045v050v15v41520v215v33v535203010[45][50][10][¥][¥]绿色为从U到V-U的边，选(v0,v2)把v2加入U845v050v15v41520v215v33v535203010[¥][45][25][50]选(v2,v3)，把v3加入U45v050v15v41520v215v33v535203010[45][45][¥]选(v3,v1)，把v1加入U45v050v15v41520v215v33v535203010[¥][45]选(v0,v4)，把v4加入U45v050v15v41520v215v33v535203010910图选择邻接矩阵表示法，其中关系矩阵的对角线初值均取0。算法中，将放入集合Ｕ中结点对应的关系矩阵中对角线元素值修改为1；另外设置一个数组dist，dist[ｉ]用于存放v0到顶点vｉ的最短路径及其最短路径长度（计算过程中为距离值）∶

ypedefstruct{ AdjTypelength; /*最短路径长度*/ intprevex; /*从v0到达vi(i=1,2,…n-1)的最短路径上vi的前趋顶点*/}Path;Path*dist;存储结构11修正距离值方法的精化在加入顶点vmin为中间顶点后，如果dist[i].length>dist[min].length+G.arcs[min][i]，则将顶点vi的距离值改为：dist[min].length+G.arcs[min][i]并修改路径上vi的前趋顶点：dist[i].prevex=min。

12①．初始时，集合U中只有顶点v0。结果dist[n]为{{0,0},{50,0},{10,0},{MAX,-1},{45,0},{MAX,-1}}②．在集合V-U中找出距离值最小的顶点v2，将顶点v2加入集合U中。结果dist[n]为{{0,0},{50,0},{10,0},{MAX,-1},{45,0},{MAX,-1}}③．按min=2调整集合V-U中顶点的距离值。因为dist[1].legth=50，dist[2].length+graph.arcs[2][1]=10+MAX，因此，顶点v1的距离值不需要调整。因为dist[3].length=MAX，dist[2].length+graph.arcs[2][3]=10+15=25，因此，顶点v3的距离值调整为25，其前趋顶点为v2。同理，顶点v4，v5的距离值不需要调整。结果dist[n]为{{0,0},{50,0},{10,0},{25,2},{45,0},{MAX,-1}}在数组dist上模拟算法13④．同理在集合V-U中找出当前距离值最小的顶点v3，并调整集合V-U中顶点的距离值。结果dist[n]为{{0,0},{45,3},{10,0},{25,2},{45,0},{MAX,-1}}⑤．在集合V-U中找出当前距离值最小的顶点v1。并调整集合V-U中顶点的距离值。结果dist[n]为{{0,0},

{45,3},{10,0},{25,2},{45,0},{MAX,-1}}⑥．在集合V-U中找出当前距离值最小的顶点v4。并调整集合V-U中顶点的距离值。结果dist[n]为{{0,0},{45,3},{10,0},{25,2},{45,0},{MAX,-1}}⑦．没有可以再加入集合U的顶点了，说明从顶点v0到顶点v5之间无路径相通。过程结束。在数组dist上模拟算法（续）14

由数组dist的prevex字段得到顶点v0到各顶点的最短路径{{0,0},{45,3},{10,0},{25,2},{45,0},{MAX,-1}}如从v0到v1的最短路径，dist[1].prevex=3可知路径上顶点v1的前一个顶点是v3，dist[3].prevex=2可知路径上顶点v3的前一个顶点是v2，dist[2].prevex=0可知路径上前一个顶点是v0，即最短路径为(v0,v2,v3,v1)。voidinit(GraphMatrix*pgraph,Pathdist[]){inti;dist[0].length=0;dist[0].prevex=0;pgraph->arcs[0][0]=1;/*用矩阵对角线元素记录集合U，为1表示在U中。*/for(i=1;i<pgraph->n;++i){/*初始化V-U中顶点的距离值*/

dist[i].length=pgraph->arcs[0][i];if(dist[i].length!=MAX)dist[i].prevex=0;elsedist[i].prevex=-1;}}15初始化dist[]voiddijkstra(GraphMatrix*graph,Pathdist[]){inti,j,mv,n=graph->n;AdjTypeminw;init(graph,dist);/*初始化，集合U中只有顶点v0*/for(i=1;i<n;++i){minw=MAX;mv=0;

for(j=1;j<n;++j)/*在V-U中选出距v0最近的顶点*/if(graph->arcs[j][j]==0&&dist[j].length<minw){mv=j;minw=dist[j].len;}if(mv==0)break;/*v0与V-U的顶点不连通，结束*/graph->arcs[mv][mv]=1;/*顶点mv加入U*/for(j=1;j<n;++j){/*调整V-U顶点的已知最短路径*/if(graph->arcs[j][j]==0&&/*为V-U的顶点*/dist[j].length>dist[mv].length+graph->arcs[mv][j]){dist[j].prevex=mv;/*调整已知最短路径信息*/dist[j].length=dist[mv].length+graph->arcs[mv][j];}}}}16Dijkstra算法17算法分析算法中的初始化部分的时间复杂度为O(n)，求最短路径部分由一个大循环组成，其中外循环运行n-1次，内循环为两个，均运行n-1次，因此，算法的时间复杂度为O(n2)。另外需要注意，在算法中改变了关系矩阵中的初始状态，如果要求算法不能破坏原始数据，就需要另外增加数据结构记录Ｕ集合的值。空间代价是Ｏ（ｎ）．189.5.2Floyd算法功能：求带权图每一对顶点间的最短路径基本思想：图采用邻接矩阵作为存储结构。把关系矩阵看成是没有经过任何中间结点，直接可以到达的每一对顶点间的最短路径。然后按结点在结点表中的顺序，每次考虑增加一个新的结点，在允许这个结点作为中间结点的条件下，计算每一对顶点间的最短路径的缩短变化。直到把所有结点都考虑进去为止，结果得到每一对顶点间的最短路径。19数据结构

为了在算法中不破坏原始的关系矩阵，需要定义一个与关系矩阵同样大小，以关系矩阵作为其初始状态的矩阵，用于存放处理中每对顶点间的距离值（或最短路径长度）。为了保存全部最短路径的轨迹，需要另外设计一个与关系矩阵同样大小的整数矩阵，存放vi到vj最短路径上vi的后继顶点的下标值。把它们封装在下面定义的结构类型ShortPath中：

typedefstruct{ AdjType*a[];/*存放每对顶点间最短路径长度*/ int*nextvex[];/*存放vi到vj最短路径上vi的后继顶点的下标值*/}ShortPath;voidFloyd(GraphMatrix*pgraph,ShortPath*ppath){inti,j,k,n=pgraph->n;for(i=0;i<n;++i)for(j=0;j<n;++j){if(pgraph->arcs[i][j]!=MAX)ppath->nextvex[i][j]=j;elseppath->nextvex[i][j]=-1;ppath->a[i][j]=pgraph->arcs[i][j];/*复制邻接矩阵*/}for(k=0;k<n;++k)for(i=0;i<n;++i)for(j=0;j<n;++j){if(ppath->a[i][k]==MAX||ppath->a[k][j]==MAX)continue;if(ppath->a[i][j]>ppath->a[i][k]+ppath->a[k][j]){ppath->a[i][j]=ppath->a[i][k]+ppath->a[k][j];ppath->nextvex[i][j]=ppath->nextvex[i][k];}

}}20Floyd算法21代价分析算法中初始化部分由一个两重循环组成，其中外循环运行n次，内循环也运行n次，初始化部分的时间复杂度为O(n2)。迭代生成最短路径长度矩阵A和路径矩阵nextvex的部分为三重循环的嵌套，其时间复杂度为O(n3)。Floyd算法的时间复杂度为O(n3)。

空间代价是Ｏ（ｎ2）（比较大）。22例题用Floyd方法求图G10各顶点间的最短路径长度。23初始状态24加入V025加入V126加入V227加入V328例如，想知道v0到v1的最短路径：由A[0][1]可知v0到v1的最短路径长度为45，路径由nextvex[0][1]=2可知顶点v0的下一顶点为v2，由nextvex[2][1]=3可知v2的下一顶点为v3，由nextvex[3][1]=1可知v3的下一顶点为v1，因此从v0到v1的最短路径为v0→v2→v3→v1路径的查找29本讲重点：图中从一个顶点到另一个顶点间路径长度最短的路径称为两个顶点间的最短路径。本章介绍了从顶点v0出发到其它顶点最短路径的Dijkstra算法和求每一对顶点间的最短路径的Floyd算法。讨论：动态规划算法*有些问题在分解时会产生大量的子问题，同时分得的子问题界限不清，互相交叉，因而在解这类问题时，将可能重复多次解同一个子问题。解决的方法可以在解决每个子问题后把它的解（包括其子子问题的解）保留在一个表格中，若遇到求与之相同的子问题的解时，就可以从表中把解找出来直接使用。本书所见过的运用动态规划法的算法有：所有结点间的最短路径算法（算法９．７）及最佳二叉排序树的构造算法（算法７．５）。30给定排序的关键码集合{key1,key2,…,keyn}和两个权集合{p1,…,pn}和{q0,q1…,qn},其中pi是检索内部结点i的概率,

qj是被检索关键码属于外部结点j的关键码集合的概率.问题

:要求构造一棵最佳二叉排序树,即构造出一棵二叉排序树,使下面的函数达到最小(E(n)一定也达到最小)：上式称为包含n个内部结点和n+1个外部结点的二叉排序树的花费,记作C(0,n).性质：最佳二叉排序树里的任何子树都最佳.31回顾：不等概率的最佳二叉排序树的构造花费的计算在构造T(i,j)时,对所有i<k≤j,

T(i,k-1)和T(k,j)都已存在,而且已知相应花费C(i,k)和C(k,j).对每个k,以keyk

为根,

T(i,k-1)和T(k,j)为左右子树的二叉树的花费为:

Ck(i,j)=W(i,j)+C(i,k-1)+C(k,j)

(结点增加一层).从所有可能k中选择使Ck(i,j)达到最小的那个k,与之对应树就是T(i,j),其根R(i,j)=k.新树的代价可以由构造它的已知最佳二叉排序树的代价算出：C(i,j)=W(i,j)+minikj(C(i,k-1)+C(k,j)).NOTE:T(i,i)为不包含任何内部结点,仅仅由权值为qi的外部结点构成,C(i,i)=0.32数组p存放内部结点的权(p[1],…,p[n])；数组q存放外部结点的权(q[0],…,q[n])；c[i][j]保存T(i,j)的花费;w[i][j]保存T(i,j)的权;r[i][j]保存T(i,j)的根.构造好的最佳二叉排序树的总花费存放在c[0][n]；r[0][n]是根结点的编号。根据r[0][n]的值，就可以确定两棵子二叉树的根在那里：33数据的存储w: 4121417 0358 0014 0001直接算出r: 0100 0020 0003 0000c: 01200 0050 0004 0000第一步r: 0110 0022 0003 0000c: 012190 00512 0004 0000第二步r: 0111 0022 0003 0000c: 0121929 00512 0004 0000第三步计算结果:34P:{5,1,2}Q:{4,3,1,1}C(i,j)=W(i,j)+minikj(C(i,k-1)+C(k,j)).

1，求着色问题近似解的贪心法。

2，构造最小生成树的prim算法（算法９．5）。这里的条件是所有权都是正数，在遇到带有负权边的图时，这样做就可能产生错误的结果。

3，Ｄｉｊｋｓｔｒａ的最短路径算法（算法９．６）求从源点到其他各结点的最短路径。这里的条件是所有权都是正数，在遇到带有负权边的图时，这样做就可能产生错误的结果。

35贪心法动态规划法与贪心法的相同点两者的相同点是