数据结构：最短路径算法.ppt
1,2023/10/21,图算法（二）,最短路经Shortest Path,青岛理工大学acm,2023/10/21,2,Dijkstra算法练习题链接http:/,2023/10/21,3,这个链接是Dijskra算法的动态演示,2023/10/21,4,问题:,两地之间是否有通路?若存在多条通路，哪条路最短？,最短路径问题,2023/10/21,5,单源最短路径 Single-Source Shortest Path(Dijkstra算法),所有顶点对间的最短路径问题 All-Pairs Shortest paths（Floyd算法）,最短路径问题,2023/10/21,6,单源最短路径 Single-Source Shortest Path,问题:带权有向图G（E,V),找出从给定源顶点s到其它顶点v的权最小路径。“最短路径”=最小权 路径的权是路径上所有边的权之和。例：道路图:从青岛理工到金沙滩的最短路径?,2023/10/21,7,v5,v4,v0,100,5,60,10,10,v1,v2,v3,20,50,30,图中从v0到其余各顶点之间的最短路径:v0到 v1 无 v0到 v2(v0,v2)10 v0到 v3(v0,v4,v3)50 v0到 v4(v0,v4)30 v0到 v5(v0,v4,v3,v5)60,单源最短路径,2023/10/21,8,贪心算法：若顶点序列V0,V1,Vn 是从V0到Vn的最短路，则序列 V0,V1,Vn-1 必为从V0到Vn-1的最短路。,权非负的单源最短路径算法（Dijkstra）,2023/10/21,9,基本思想：将图中所有顶点分成两组:S,V-S 一组是包括已确定最短路径的顶点的集合S，另一组是尚未确定的最短路径的顶点集V-S。S初始仅包含源v0,不断在V-S做贪心选择扩充集合S。,权非负的单源最短路径算法（Dijkstra）,2023/10/21,10,权非负的单源最短路径算法（Dijkstra）,初始时,S仅包含源v0,特殊路径：从源到G中某一顶点u且中间只经过S中顶点的路称为从源到u的特殊路径。步骤:(1)取v0加入S中(2)从V-S中取出具有当前最短路径长度的顶点w加入S中。,2023/10/21,11,v5,v4,v0,100,60,10,10,v1,v3,20,50,30,v2,v0 v1 v2 v3 v4 v5,v0 v1 v2 v3 v4 v5,权非负的单源最短路径算法（Dijkstra）,邻接矩阵,2023/10/21,12,2023/10/21,13,Dijkstra算法：,一般情况下，Distk=或者=+,设置辅助数组Dist，其中每个分量Disti 表示 当前所求得的从源点到其余各顶点 i 的最短路径的长度。,2023/10/21,14,1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。,2）修改其它各顶点的Disti值。假设求得最短路径的顶点为u，若 Distu+G.arcsuiDisti则将 Disti 改为 Distu+G.arcsui,V0和i之间存在弧,V0和i之间不存在弧,其中的最小值即为最短路径的长度。,2023/10/21,15,权非负的单源最短路径算法（Dijkstra）,#include#include#include using namespace std;const int INF=0 xfffffff;#define maxn 110int grapmaxnmaxn;/邻接矩阵存储图int premaxn;/标记这个点是否已经被选过int n,m;int distmaxn;/记录从源点到其他所有点的最短距离,2023/10/21,16,void init()/对一些数据进行初始化int i,j;for(i=1;i=n;i+)for(j=1;j=n;j+)grapij=INF;memset(pre,0,sizeof(pre);void dijkstra(int u)int i,j;for(i=1;i=n;i+)/首先求出源点到其他所有点的距离disti=grapui;preu=1;,2023/10/21,17,int x=u;for(i=1;i distj)maxs=distj;x=j;prex=1;for(j=1;j(distx+grapxj),2023/10/21,18,int main()scanf(%d%d,2023/10/21,19,所有顶点对之间的最短路径算法Floyd算法,已知一个有向图（无向图），对于每对顶点Vi！=Vj，求出它们之间的最短路径长度。解决这个问题有两种方法：（1）轮流以每个顶点为源点重复执行dijkstra算法。（2）采用Floyd算法，时间复杂度O（n3）,2023/10/21,20,P=,0 0 0,0 0 0,a2=,k=1 a1=k=2k=3,0-1 0,P1=,0 0 0,0 0 0,0 1 0,0 0 2,0 0 0,0 1 0,0 0 2,3 0 0,0 1 0,P2=,P3=,a3=,Floyd算法演示,2023/10/21,21,Floyd算法描述定义一个n阶的方阵序列：A（-1），A（0）A（1）A（n-1），其中：A（-1）ij表示顶点vi到vj的直接边长，A（-1）就是存储图的邻接矩阵EdgennA（0）ij表示从顶点vi到vj，中间顶点是v0的最短路径长度A（1）ij表示从顶点vi到vj，中间顶点序号不大于1的最短路径长度.A（k）ij表示从顶点vi到vj，中间顶点序号不大于k的最短路径长度.,2023/10/21,22,A（n-1）ij是最终求得的从顶点vi到vj的最短路径长度增加中间顶点vk后，对于图中的每一对顶vi和vj，要比较从vi到vk的最短路径长度加上从vk到vj的最短路径长度是否小于原来从vi到vj的最短路径长度，即比较A（k-1）ik+A（k-1）kj与A（k-1）ij的大小，去较小的为A（k-1）ij的值。因此我们得到递推公式为：,2023/10/21,23,Floyd算法的代码实现,#include#include#include#include#include using namespace std;const int INF=0 xfffffff;#define maxn 110int grapmaxnmaxn;/邻接矩阵存储图int n,m;int distmaxnmaxn;/记录从所有点之间的最短距离,2023/10/21,24,void init()/对一些数据进行初始化 int i,j;for(i=1;i=n;i+)for(j=1;j=n;j+)grapij=INF;void floyd()int i,j,k;for(i=1;i=n;i+)/初始化，一开始每个点与点之间的路径长度就等于grap中的长度for(j=1;j=n;j+)distij=grapij;for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(k=i|k=j)continue;if(distik+distkj distij)distij=distik+distkj;,2023/10/21,25,int main()scanf(%d%d,2023/10/21,26,关于Floyd算法的进一步分析,时间复杂度分析 在代码中我们已经看到，有一个三重嵌套的for循环，因此最内层的if执行次数为n3，所以Floyd算法的时间复杂为O(n3)，并且因为floyd算法的思想是逐渐将每一个顶点作为中间顶点，来判断能否减少任意一对顶点之间的最短路径长度，而这些点的信息我们都保存在邻接矩阵A中，而存储图信息邻接矩阵只是用来初始化A，所以改用邻接表并不能降低算法的时间复杂度。,2023/10/21,27,算法的适用范围 Floyd算法和dijkstra算法不同，Floyd算法允许图中存在有带负权值得边，但不允许有包含负权值回路算法到这里已经基本上讲完了下面给出几个例题，大家都去做，只有在做题的过程运用了这个算法，才能真正的理解这个算法。,2023/10/21,28,Poj2570 光纤网络Poj2263 重型运输这些题目都有一些转弯，所以看题时一定要认真思考题目给出的信息，找到只要矛盾点。,2023/10/21,29,Welcome to QTECH ACMER,
