毕业答辩-地图上两点间最短道路标定的实现.ppt

2014-6-7,地图上两点间最短道路标定的实现,指导老师：答辩人：学号：班级：通信1001,地图上两点间最短道路标定的实现,主要内容,地图上两点间最短道路标定的实现,主要内容,地图上两点间最短道路标定的实现,课题简介,1.选题背景,地图上两点间最短道路标定的实现,地图数据增大,移动终端普及,其他原因,例如：使用方便功能多效率高,地图上两点间最短道路标定的实现,课题简介,2.编程运行环境,VisualStudio2008,VC+下最短路径算法的实现,MFC图像界面应用程序的编写,地图上两点间最短道路标定的实现,主要内容,地图上两点间最短道路标定的实现,总体流程,地图上两点间最短道路标定的实现,主要内容,地图上两点间最短道路标定的实现,系统具体设计及实现,1.最短路径算法Dijkstra算法将网络节点分为未标示节点、临时标示节点和已标示节点3种类型。开始网络搜索时，所有节点首先初始化为未标示节点，在搜索过程中和最短路径节点相连通的节点记为临时标示节点，每一次循环从临时节点找到的距源点路径最短的节点记为已标示节点，直到找到目标节点或者所有节点都成为已标示节点为止。,地图上两点间最短道路标定的实现,系统具体设计及实现,S,V0,V-S,V1,V2,V3,V4,V5,1初始时，S=V0，V-S=V1,V2,V3,V4,V5,从V0到V-S中剩余各点Vi的路径长度分别为Cost0i。假设当前从V0出发的最短路径的终点是V2。,地图上两点间最短道路标定的实现,系统具体设计及实现,S,V0,V-S,V1,V3,V4,V5,V2,2将V2加入S，同时修改V0到V-S中剩余各点的路径长度。,地图上两点间最短道路标定的实现,系统具体设计及实现,S,V0,V-S,V1,V3,V4,V5,V2,3修改过程如下：以求取V0到V1的最短路径长度为例，如果二者之间存在一条路径（V0,V2,V1）的长度比原来（V0,V1）的弧长更短，则用（V0，V2，V1）代替原来的（V0,V1）成为当前的最短路径。4修改V0到V3，V0到V4，V0到V5的最短路径长度依此操作。,地图上两点间最短道路标定的实现,系统具体设计及实现,S,V0,V-S,V1,V3,V5,V2,5此轮操作完成后，若当前最短路径中的终点是V4，则将V4加入S，同时修改V0到V-S中剩余各点的路径长度。修改过程如下：以求取V0到V1的最短路径长度为例，如果二者之间存在一条路径（V0，V4，V1）的长度比原来（V0,V2,V1）的更短，则用（V0，V4，V1）替代原来的（V0,V2,V1）成为当前的最短路径。6修改V0到V3，V0到V5的最短路径长度依此操作。,V4,地图上两点间最短道路标定的实现,系统具体设计及实现,S,V0,V-S,V1,V5,V2,7此轮操作完成后，若当前最短路径中的终点是V3，则将V3加入S，同时修改V0到V-S中剩余各点的路径长度。修改过程如下：以求取V0到V1的最短路径长度为例，如果二者之间存在一条路径（V0，V3，V1）的长度比原来（V0，V4，V1）的更短，则用（V0，V3，V1）替代原来的（V0，V4，V1）成为当前的最短路径。8修改V0到V3的最短路径长度依此操作。,V4,V3,地图上两点间最短道路标定的实现,系统具体设计及实现,S,V0,V-S,V1,V2,9此轮操作完成后，若当前最短路径中的终点是V5，则将V5加入S，同时修改V0到V-S中剩余各点的路径长度。修改过程如下：以求取V0到V1的最短路径长度为例，如果二者之间存在一条路径（V0，V5，V1）的长度比原来（V0，V3，V1）的更短，则用（V0，V5，V1）替代原来的（V0，V3，V1）成为当前的最短路径。10此时，当前最短路径中的终点是V1，则将其加入S。,V4,V3,V5,地图上两点间最短道路标定的实现,系统具体设计及实现,2.道路节点设置总共放了46个节点（1）设置各个节点的横纵坐标（2）初始化节点间的距离其中相同节点设置为0；不相连节点设置为无穷大,地图上两点间最短道路标定的实现,系统具体设计及实现,3.路径标定实现（1）寻找离起点和终点最近的两个节点进行连线（2）计算这两段距离（图中绿色路径）（3）计算两个节点间的距离（图中红色路径）（4）将绿色与红色路径相加得出最终路径,地图上两点间最短道路标定的实现,主要内容,地图上两点间最短道路标定的实现,不足与改进,1.由于路径标定实现的思路原因，在数据没有达到足够数量的时候会出现一些错误的路径。（1）计算出的路径穿过建筑物,地图上两点间最短道路标定的实现,不足与改进,（2）计算出的路径并不是真正意义上的最短路径,地图上两点间最短道路标定的实现,不足与改进,2.解决方案：尽可能多的设置节点，如第