第七章 最短路径-SPL.ppt

最短路径 我们需要解决的问题 例1：输入起点，终点，求其最短路径？ 如3-5 思路 Relaxation(松弛操作) 松弛操作的原理是著名的定理：“三角形两边之和大于第三边”，在信息学中我们叫它三角不等式。所谓对i,j进行松弛，就是判定是否d[j]d[i]+w[i,j]，如果该式成立则将d[j]减小到d[i]+w[i,j]，否则不动。 procedure relax(u,v,w:integer);//不需要单独写成过程 begin if dis[u]+wdis[v] then begin dis[v]:=dis[u]+w; pre[v]:=u; end end; 图的常用数据结构结构----邻接矩阵（静态） 图的常用数据结构结构----邻接表（动态） 邻接表的定义 n个顶点e条边的有向图，它的邻接表表示中必然有n个顶点结点和e条边的结点。 Const maxvertexnum=100; { 设置最大顶点数 } Type vertextype=char; { 设置顶点类型 } link=^node; node=record {连接表结点定义} adj:integer; {邻接点域} next:link; { 结点链域 } end; vnode=record { 图的顶点结点定义 } vertex: vertextype; { 顶点域 } firstedge: link; { 表头链域 } end; graph=array[1..maxvertexnum] of vnode; Contents 1、Dijkstra算法 问题分析 处理步骤 处理步骤 代码框架 代替集合S，用来保存已求得最短路径的终点集合，即如果s[j]=0表示顶点Vj不在集合中，反之，s[j]=1表示顶点Vj已在集合中）。 Procedure Dijkstra(GA,dist,path,i)； {求Vi到图G中其余顶点最短路径，GA为图邻接矩阵，dist和path为变参，path的基类型为集合} Begin For j:=1 To n Do Begin {初始化} If ji Then s[j]:=0 Else s[j]:=1； dist[j]:=GA[i,j]； If dist[j]maxint Then path[j]:=[i]+[j] Else path[j]:=[ ]； End； 代码框架 算法局限性 对于不含负权边的图求单源最短路径，Dijkstra算法是最高效的。 Dijkstra 算法只能适合权为正值的情况,但当权为负值时，是Dijkstra 算法爱莫能助？ 分析：Dijkstra每次选的是当前能连到的边中权值最小的，在正权图中这种贪心是对的，但是在负权图中就不是这样了。沿着一个负权回路再走一次总是能更小，…… 练习：最优乘车(travel) 【问题描述：】 H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1…S公园巴士站的编号为N。写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程中换车的次数最少。【输入：】第一行有两个数字M和N(1=M=100 1N=500），表示开通了M条单程巴士线路，总共有N个车站。从第二行到第M+1行依次给出了第1条到第M条巴士线路的信息。其中第i+1行给出的是第i条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间用一个空格隔开。【输出:】 一行。如果无法乘巴士从饭店到达S公园，则输出N0，否则输出你的程序所找到的最少换车次数，换车次数为0表示不需换车即可到达·【样例输入：】3 76 74 7 3 62 1 3 5【样例输出：】2 2、Bellman Ford Bellman-Ford是在Dijkstra算法上的改进。在dijstra基础上，判断是否有负权回路再做一次松弛操作，也就是说如果存在一条边（u,