图的最短路.ppt

1、图的最短路径,迪杰斯特拉（Dijkstra）算法,10,max,50,30,60,0,0,2,4,3,5,0,2,4,3,0,max,10,50,30,60,0,2,4,0,max,10,50,30,90,0,2,0,max,10,60,30,100,初始化,输出结果,For i1 to n do,disticostv,i;,distimax,Y,N,pathiv+i,处理数组dist和集合S,pathi ,Sv,not(i in s) and distiwm,not(i in s) and distidistj+costj,i,for k:=1 to n-1 do begin wm:=max

2、;j:=0; for i:=1 to n do if not(i in s)and(distiwm) then begin j:=i;wm:=disti;end; s:=s+j; for i:=1 to n do if not(i in s)and(distj+costj,idisti) then begin disti:=distj+costj,i;pathi:=pathj+char(48+i);end; end;,弗洛伊德（Floyd）算法 求Vi到Vj的最短路径 如果costi,jmax ,从Vi到Vj存在一条长度为costi,j的路径，但该路径不一定是最短路径，尚需进行n次试探。,首先

3、，考虑路径（Vi,V1,Vj）是否存在（即判别弧（Vi,V1）和（V1，Vj）是否存在）。 如果存在，则比较（Vi,Vj）与 （Vi,V1,Vj）的路径长度较短者为从Vi到Vj的中间顶点的序号不大于1的最短路径。 在路径上再增加一个顶点V2，也就是说，如果（Vi,V2)和（V2,Vj)分别是当前找到的中间顶点不大于1的最短路径，那么（ Vi,V2,Vj)就有可能是Vi到Vj的中间顶点的序号不大于2的最短路径。将它和中间顶点不大于1的最短路径相比较，从中选出中间顶点不大于2的最短路径。 再增加顶点V3，继续进行试探，依此类推，直到经过n次比较后，最后求得Vi到Vj的中间顶点的序号不大于n的最短路

4、径。,for k:=1 to n do for i:=1 to n do for j:=1 to n do if lengi,k+lengk,jlengi,j then begin lengi,j:=lengi,k+lengk,j; pathi,j:=pathi,k+copy(pathk,j,2,length(pathk,j)-1); end;,图的中心点,如图有6个村（0号5号），边的长度表示各村间的距离，现在要设置一所学校，为了尽量缩短学生上学所走的路程，学校应满足以下两个条件：（1）学校要建在村里；（2）让上学所走路程最远的学生所走距离尽可能的小。 问题1：请问学校应建在哪个村？ 问题2

5、：如果要建2个学校请问学校应建在哪2个村？,图的中央点,如图有6个矿区（0号5号），边的长度表示各矿区间的距离。各矿区日产量如下： 0号矿区1000吨； 1号矿区3000吨； 2号矿区2000吨； 3号矿区5000吨； 4号矿区4000吨； 5号矿区3000吨；现在要设置一所矿厂，为了尽量减少各矿区到矿厂的运费，矿厂应满足以下两个条件：（1）矿厂要建在矿区里；（2）让各矿区每天的运费总额尽可能的小。 请问学校应建在哪个矿区？,Car的旅行路线(30分) 问题描述又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机

6、场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。,那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。 任务找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。 样例输入13 10 1 31 1 1 3 3 1 302 5 7 4 5 2 18 6 8 8 11 6 3输出：47.55,BellmanFord算法,BellmanFord算法与Dijkstra算法一样，用于求解单源点最短路径问题。BellmanFord算

7、法除了可求解权边非负的问题外，还可以解决存在负权边的问题，而Dijkstra算法只能处理边权均非负的问题，因此BellmanFord算法的适用面要广泛一些。,BellmanFord算法的时间复杂度为O(VE),比Dijkstra算法的时间复杂度O(VlogV) 高,所以常常被众多的大学算法教科书所省略。,BellmanFord算法思想,BellmanFord算法能在更普遍的情况下(存在负权边)解决单源点最短路径问题。对于给定的带权(有向或无向)图G=(V，E)，其源点为s，加权函数w是边集E的映射。对图G运行BellmanFord算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权

8、回路。若存在负权回路，单源点最短路径问题无解；若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径值dv,BellmanFord算法流程,分为三个阶段： (1)初始化：将除源点外的所有顶点的最短距离估计值 dv+，ds0； (2)迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集v中的每个顶点v的最短距离估计值逐步逼近其最短距离； (3)检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在dv中。,B:=true; for k:=1 to n-1 do dk:=max; ds:=0; for k:=1 to n-1 do begin for i:=1 to n do for j:=1 to n do if datai,jmaxint then if d