南邮acm算法与数据结构设计(2010-2011-2第6讲)1.ppt

ACM算法与数据结构设计 班 级 ：仙林校区ACM选修班 上课地点和时间 理论：教2－402：星期3 （18:30开始） 实践：（仙林）计算中心 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 一维数组d d[i]中存放从源点v0到i的当前最短路径的长度，该路径上除顶点i自身外，其余顶点都属于S，并且这是所有这些路径中的最短者。（用来描述从源点v0到i的最短路径上权值的上界，称为最短路径估计（shortest-path estimate）） 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 第6讲:ACM竞赛之图论模型与算法 6.4 最短路问题：Djikstra算法 迪杰斯特拉（Dijkstra）算法思想 初始状态时，集合S中只有一个源点，设为顶点v0。首先产生从源点v0到它自身的路径，其长度为0，将v0加入S。 算法的每一步上，按照最短路径值的非减次序，产生下一条最短路径，并将该路径的终点t?V-S加入S。 直到S＝V时算法结束。 6.4 最短路问题：Djikstra算法 一维整型数组path path[i]给出从v0到顶点i的最短路径上，位于顶点i前面的那个顶点。 例如，从v0到v1的最短路径为（v0,v2,v3,v1），则path[1]=3，path[3]=2，path[2]=0 一维布尔数组s 若s[i]为true，表示顶点i在S中，否则表示i在V－S中。? 6.4 最短路问题：Djikstra算法 当前最短路径 在算法执行中，一个顶点t?V－S的当前最短路径，是一条从源点v0到顶点t的路径 （v0，?，u，t） 在该路径上，除顶点t 外，其余顶点的最短路径都已求得，即路径（v0，?，u）上所有顶点都属于S。 （v0，?，u，t）是所有这些路径中的最短者。 6.4 最短路问题：Djikstra算法 (0)初始化 （1）s[v0]=true （2）d[i] （3）path[i]: 若v0,vi?E，则 path[i]=0， 否则 path[i]=-1 6.4 最短路问题：Djikstra算法 (1)求第一条最短路径 第一条最短路径是所有最短路径中的最短者，它必定只包含一条边(v0，k)，并满足： 6.4 最短路问题：Djikstra算法 (2)更新d和path 将顶点k加入S，并对所有的i∈V-S修正d的值 6.4 最短路问题：Djikstra算法 (1)求第一条最短路径 第一条最短路径是所有最短路径中的最短者，它必定只包含一条边(v0，k)，并满