数据结构 第7章 图

《数据结构 第7章 图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章图5.1基本概念5.2图的存储结构5.3图的遍历5.4拓扑排序5.5关键路径5.6最短路径5.7最小支撑树5.6最短路径问题两顶点间可能存在多条路径，每条路径经过的边数不同，每条路径的各边权值之和也不同。从一个指定的顶点到达另一指定顶点的路径上各边权值之和最小的路径被称为最短路径，这类问题亦称为最短路径问题。单源(由一个指定顶点到其他顶点)最短路径无权最短路径正权最短路径每对顶点之间的最短路径问题5.6.2正权最短路径问题给定一个带权图D与源点v，求从v到D中其它顶点的最短路径,限定各边的权值为正实数。v0v1v2283Dijkstra算法思想按路径长

2、度非递减的次序，逐步产生最短路径的算法，解决正权单源最短路径问题。首先求出从源点v出发，长度最短的一条最短路径；再参照它求出长度次短的一条最短路径；依此类推，直到求出从顶点v到其它各顶点的最短路径为止。Dijkstra算法描述初始时（S为初始顶点）,Ds=0且i≠S，有Di=＋∞。①在未访问顶点中选择Dv最小的顶点v，访问v，令S[v]=1。②依次考察v的邻接顶点w，若Dv+weight())。③重复①②，直至所有顶点被访问。为了找到最短路径，使用path[]存储从S到i的最短路径上最后一

3、个经历的顶点。[例]132581020453012023401234024310∧5134∧3038∧225410∧02024412∧spathdist0000003421∞∞∞0∞1325810204530120234①在未访问顶点中选择Dv最小的顶点v，访问v，令S[v]=1。②依次考察v的邻接顶点w，若Dv+weight())。③重复①②，直至所有顶点被访问。013302343∞∞1325810204530120234spathdist1000003421030∞3∞v0v001330

4、2343∞∞1325810204530120234spathdist1000103421030∞3∞v0v0spathdist100010342103028311v0v0v1v1325813300234302811132581020453012023403421spathdist1100103028311v0v1v1v013258102045301202343120415813234231103421spathdist1100102315311v0v3v1v31325810204530120234312041581323423111204158132342311

5、31325810204530120234spathdist1101102315311v0v3v1v3spathdist111110342102315311v0v3v1v3Dijkstra算法:按照非递减顺序依次得到各顶点的最小路径长度。120415813234231131325810204530120234正权单源最短路径问题的Dijkstra算法：算法DShortestPath(n,v)/*计算v到其他各顶点的最短路径*/DSPath1[初始化]FORi=1TOnDO(path[i]-1.dist[i]max.s[i]0.)//数组s[i]记录i是否被访

6、问过dist[v]0.s[v]1.padjacent(Head[v]).uv.//u为即将访问的顶点1325810204530120234DSPath1[初始化]FORi=1TOnDO(path[i]-1.dist[i]max.s[i]0.)dist[v]0.s[v]1.padjacent(Head[v]).uv.//u为即将访问的顶点－1－1－1－1－1spathdisk0000003421∞∞∞∞∞－1－1－1－1－1spathdist1000003421∞∞∞0∞01234024310∧5134∧3038∧225410∧0202441

7、2∧p1325810204530120234DSPath2[求从初始顶点v到其他各顶点的最短路径]算法DSPath2第1部分FORj=1TOn-1DO//求从v到其他各顶点的最短路径(WHILEpDO//修改u邻接顶点的path[]值和dist[]值(kVerAdj(p).IF(s[k]1ANDdist[u]+cost(p)

8、0∧5134∧3038∧