《迪杰斯特拉算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《迪杰斯特拉算法ppt课件.ppt（15页珍藏版）》请在三一办公上搜索。
1、迪杰斯特拉算法实现,第九组11123529-罗凯耀11123575-王鸣,迪杰斯特拉-算法思想,按从某顶点到其它顶点的路径长度递增的方式,逐渐求到各顶点的最短路径。,设给定源点为Vs，S为已求得最短路径的终点集，开始时令S=Vs 。当求得第一条最短路径(Vs ，Vi)后，S为Vs，Vi 。根据以下结论可求下一条最短路径。 设下一条最短路径终点为Vj ，则Vj只有： 源点到终点有直接的弧； 从Vs 出发到Vj 的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj 。 若定义一个数组distn，其每个disti分量保存从Vs 出发中间只
2、经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即： disti=Min distk| VkV-S 利用上述公式就可以依次找出下一条最短路径。,迪杰斯特拉-算法思想,源,迪杰斯特拉算法-数据组织,源,有n个结点的网络,数据源 已确定结点集 S 待选结点集 V-S 结点临时最短路径长度 结点临时最短路径,迪杰斯特拉算法步骤, 令S=Vs ，用带权的邻接矩阵表示有向图，对图中每个顶点Vi按以下原则置初值： 选择一个顶点Vj ，使得： Distancej=Min Distancek| VkV-S Vj就是求得的下一条最短路径终点，
3、将Vj 并入到S中，即S=SVj 。 对V-S中的每个顶点Vk ，修改distk，方法是：若Distancej+WjkDistancek，则修改为：Distancek=Distancej+Wjk (VkV-S ) 重复，直到S=V为止。,迪杰斯特拉算法实现,void Dijkstra(MGraph g,int start, int end) int distMAXV, pathMAXV; int sMAXV; int mindis, i, j, u; for(i = 0; i g.n; i +) disti = g.edgesstarti;/dist数组初始化 si = 0; if(g.edg
4、esstarti INF) pathi = start; else pathi = -1; / path数组初始化 sstart = 1; /顶点start加入顶点集合spathstart = 0; for(i = 0; i g.n; i +)/选择不在集合s中且具有最短路径的顶点 mindis = INF; for(j = 0; j g.n; j +) if(sj = 0 ,su = 1;/将顶点u加入集合 for (j = 0; j g.n; j +)/修改dist和path if (sj = 0) if (g.edgesuj INF) ,运算过程表,邻接矩阵,图,数据源 邻接矩阵 已确定
5、结点集 S 待选结点集 V-S 结点临时最短路径长度 Distance数组 结点临时最短路径 Path数组,Dijkstra算法-数据组织,运算过程表,Dijkstra算法例子,邻接矩阵,图,例：计算从A点出发的单源最短路径,运算过程表,Dijkstra算法例子,邻接矩阵,图,例：计算从A点出发的单源最短路径,运算过程表,Dijkstra算法例子,邻接矩阵,图,例：计算从A点出发的单源最短路径,运算过程表,Dijkstra算法例子,邻接矩阵,图,例：计算从A点出发的单源最短路径,运算过程表,Dijkstra算法例子,邻接矩阵,图,例：计算从A点出发的单源最短路径,运算结果,Dijkstra算法例子,邻接矩阵,图,通过Distance数组得到最短路径长度： D: 22通过对Path数组的反向搜索得到最短路径，如D结点相对于源点A的最短路径： DFCA,例：计算从A点出发的单源最短路径,Dijkstra算法的主要执行是： 数组变量的初始化：时间复杂度是O(n) ； 求最短路径的二重循环：时间复杂度是O(n2) ； 因此，整个算法的时间复杂度是O(n2) 。,Dijkstra算法算法分析,
