算法分析与设计_求带权最短路径_课程设计

《算法分析与设计_求带权最短路径_课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《算法设计与分析》课程设计报告题目：求带权最短路径专业：****学号：****姓名：****指导教师：***　成绩：＊＊年＊月＊＊日一、问题描述给定n个顶点的带权有向图G=(V,E),W=()为G的带权邻接矩阵。定义如下：=对于每一对顶点u，vV，试用动态规划方法，求从u到v的带权最短路径长度，其中路径权值为这条路径所有边上的权值之和。二、设计说明1、基本要求：利用Dijkstra算法，寻找有向图中最短路径。2、算法说明：Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中最短路径问题。Dijkstra算法的输入包含了一个有权重的有向图G，以及

2、G中的一个来源顶点S。我们以V表示G中所有顶点的集合。图中的每一个边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。假设E为所有边的集合，而边的权重则由权重函数w:E→[0,∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e.最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。这个算法是通过为每个顶点v保留目前为止所找到的从s到v的

3、最短路径来工作的。初始时，源点s的路径长度值被赋为0（d[s]=0），同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]=∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者是无穷大（如果路径不存在的话）。Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到v的最短路径可以通过将边(u,v)添加到s到u的尾部来拓展。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s

4、到v最短路径的花费。这个算法经过适当的组织因而当d[u]达到它最终的值的时候，每条边(u,v)都只被拓展一次。算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。3、算法思想：（1）设S为最短距离已确定的顶点集（看作红点集），V-S是最短距离尚未确定的顶点集（看作蓝点集）。①初始化：初始化时，只有源点s的最短距离是已知的(SD(s)=0)，故

5、红点集S={s}，蓝点集为空。②重复以下工作，按路径长度递增次序产生各顶点最短路径。在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证按路径权重递增的次序来产生各顶点的最短路径。当蓝点集中仅剩下最短距离为∞的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。注意：①若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。②从源点s到终点v的最短路径简称为v的最短路径；s到v的最短路径长度简称为v的最短距离，并记为SD(v)。（2）在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集根据按长度递增序产生最短路径的思想，当前最

6、短距离最小的蓝点k的最短路径是：源点，红点1，红点2，…，红点n，蓝点k。距离为：源点到红点n最短距离+<红点n,蓝点k>边长为求解方便，设置一个向量D[0．．n-1]，对于每个蓝点v∈V-S，用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点，则必为红点)的"最短"路径长度（简称估计距离）。若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i]i∈V-S}，则D[k]=SD(k)。初始时，每个蓝点v的D[c]值应为权w，且从s到v的路径上没有中间点，因为该路径仅含一条边。注意：在蓝点集中选择一个最短距

7、离最小的蓝点k来扩充红点集是Dijkstra算法的关键。（3）k扩充红点集s后，蓝点集估计距离的修改将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。对于任意的蓝点j，若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径：P=。且D[j]减小的新路径P只可能是由于路径和边组成。所以，当length(P)=D[k]+w小于D[j]时，应该用P的长度来修改D[j]的值。例：如下