迪杰斯特拉算法讲课教案.ppt

《迪杰斯特拉算法讲课教案.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、迪杰斯特拉算法实现第九组11123529-罗凯耀11123575-王鸣迪杰斯特拉--算法思想按从某顶点到其它顶点的路径长度递增的方式,逐渐求到各顶点的最短路径。设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs}。当求得第一条最短路径(Vs，Vi)后，S为{Vs，Vi}。根据以下结论可求下一条最短路径。设下一条最短路径终点为Vj，则Vj只有：◆源点到终点有直接的弧；◆从Vs出发到Vj的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj。若定义一个数组dist[n]，其每个di

2、st[i]分量保存从Vs出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即：dist[i]=Min{dist[k]

3、Vk∈V-S}利用上述公式就可以依次找出下一条最短路径。迪杰斯特拉-算法思想源迪杰斯特拉算法--数据组织源有n个结点的网络数据源已确定结点集S待选结点集V-S结点临时最短路径长度结点临时最短路径迪杰斯特拉算法—步骤①令S={Vs}，用带权的邻接矩阵表示有向图，对图中每个顶点Vi按以下原则置初值：②选择一个顶点Vj，使得：Distance[j]=Min{Distance[

4、k]

5、Vk∈V-S}Vj就是求得的下一条最短路径终点，将Vj并入到S中，即S=S∪{Vj}。③对V-S中的每个顶点Vk，修改dist[k]，方法是：若Distance[j]+Wjk∈E，wsi为弧上的权值∞i≠s且不属于Edist[i]=0i=s迪杰斯特拉算法—实现voidDijkstra(MGraphg,intstart,intend){intdist[MAXV],path[MAXV]

6、;ints[MAXV];intmindis,i,j,u;for(i=0;i

7、]

8、cePath4DistancePath5(n-1)DistancePathEFDBCA8253018107154úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF运算过程表邻接矩阵图数据源——邻接矩阵已确定结点集S待选结点集V-S结点临时最短路径长度——Distance数组结点临时最短路径——Path数组Dijkstra算法--数据组织已完成结点集，本次最近点ABCDEF1{A,},CDistance0¥530¥¥PathA-1AA-1-12DistancePath3Di

9、stancePath4DistancePath5(n-1)DistancePath运算过程表Dijkstra算法—例子EFDBCA8253018107154úúúúúúúúûùêêêêêêêêë饥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥0181004070158023050BACDEFBACDEF邻接矩阵图例：计算从A点出发的单源最短路径已完成结点集，本次最近点ABCDEF1{A,},CDistance0¥530¥¥PathA-1AA-1-12{A,C},FDistance020530¥12PathACAA-1C3DistancePath4DistancePat

10、h5(n-