最短路径-SPL.ppt

《最短路径-SPL.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最短路径数据结构图论51234SPAShortestPathAlgorithm我们需要解决的问题例1：输入起点，终点，求其最短路径？如3->5思路最短路径是图论中的一个重要问题，具有很高的实用价值，也是信息学竞赛中常见的一类中等难度的题目，这类问题很能联系实际，考察学生的建模能力，反映出学生的创造性思维，因为有些看似跟最短路径毫无关系的问题，也可以归结为最短路径问题来求解。在带权图G=（V，E）中，若顶点Vi,Vj是图G的两个顶点，从顶点Vi到Vj的路径长度定义为路径上各条边的权值之和。从顶点Vi到Vj可能

2、有多条路径，其中路径长度最小的一条路径称为顶点Vi到Vj的最短路径。一般有两类最短路径问题：一类是求从某个顶点（源点）到其它顶点（终点）的最短路径；另一类是求图中每一对顶点间的最短路径。对于不带权的图，只要人为的把每条边加上权值1，即可当作带权图一样处理了。Relaxation(松弛操作)松弛操作的原理是著名的定理：“三角形两边之和大于第三边”，在信息学中我们叫它三角不等式。所谓对i,j进行松弛，就是判定是否d[j]>d[i]+w[i,j]，如果该式成立则将d[j]减小到d[i]+w[i,j]，否则不动。pr

3、ocedurerelax(u,v,w:integer);//不需要单独写成过程beginifdis[u]+w

4、exnum,1..maxvertexnum]ofinteger;{图的边集}end;图的常用数据结构结构----邻接表（动态）无向图的邻接表有向图的邻接表邻接表的定义n个顶点e条边的有向图，它的邻接表表示中必然有n个顶点结点和e条边的结点。Constmaxvertexnum=100;{设置最大顶点数}Typevertextype=char;{设置顶点类型}link=^node;node=record{连接表结点定义}adj:integer;{邻接点域}next:link;{结点链域}end;vnode=rec

5、ord{图的顶点结点定义}vertex:vertextype;{顶点域}firstedge:link;{表头链域}end;graph=array[1..maxvertexnum]ofvnode;ContentsDijkstra1BellmanFord2Floyd3SPFA41、Dijkstra算法例、如下图，假设C1,C2,C3,C4,C5,C6是六座城市，他们之间的连线表示两城市间有道路相通，连线旁的数字表示路程。请编写一程序，找出C1到Ci的最短路径(2≤i≤6)，输出路径序列及最短路径的路程长度。问题分

6、析对于一个含有n个顶点和e条边的图来说，从某一个顶点Vi到其余任一顶点Vj的最短路径，可能是它们之间的边（Vi，Vj），也可能是经过k个中间顶点和k+1条边所形成的路径(1≤k≤n-2)。设图G用邻接矩阵的方式存储在GA中，GA[i,j]=maxint表示Vi，Vj是不关联的，否则为权值（大于0的实数）。设集合S用来保存已求得最短路径的终点序号，初始时S=[Vi]表示只有源点，以后每求出一个终点Vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist[1..n]用来存储当前求得的最短路径，初始时Vi，V

7、j如果是关联的，则dist[j]等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，dist[j]可能越来越小。再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边，初始时为Vi到Vj的边，如果不存在边则为空。执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为dist[m]），该元素值就是从源点Vi到终点Vm的最短路径长度，对应的path[m]中的顶点或边的序列即为最短路径。接着把Vm并入集合S中，然后以Vm作为新考虑的中

8、间顶点，对S以外的每个顶点Vj，比较dist[m]+GA[m,j]的dist[j]的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替dist[j]，同时把Vj或边（Vm，Vj）并入到path[j]中。重复以上过程n-2次，即可在dist数组中得到从源点到其余各终点的最段路径长度，对应的path数组中保存着相应的最段路径。对于上图，采用Dijkstra算法找出