基于Android的车载导航系统的研究与设计

① 初始化集合S、向量D。S={V0}，D[i]=Arcs[0][i](i=0,1,…,n-1)。
② 选择Vj,使得D[j]=min{D[i]|Vi∈V-S},S=S∪{Vi}。
③ 修改从V0出发到集合V-S上任意节点Vk的最短路径长度。若D[k]>D[j]+Arcs[j][k]，则修改D[k]为D[k]=D[j]+Arcs[j][k]。
④ 重复②、③操作n-1次，即可求得从V0到其余各顶点Vi的最短路径长度。

　　Dijkstra算法的时间复杂度是O（n2）。

　　在实际应用中往往只需要搜素从某一源点到某一或某几个特定终点的最短路径，用Dijkstra算法求解，此问题与求源点到其余各顶点的最短路径的时间复杂度相同，也为O（n2）。

4　性能测试分析

　　基于Android操作系统和ARM微处理器进行设计的车载导航系统，利用Android通用框架和与设备无关的应用程序开发平台，实现了车载导航的软件总体架构。图3为车辆定位显示的应用程序窗口。截图所示范围为厦门软件园附近，箭头为汽车所在位置。在实现的导航设备中，对导航设备的定位精度、电子地图显示速度以及在最短路径导航规划所需的时间进行性能测试。

图3　车辆定位显示的应用程序窗口

(1) 定位精度测试
　　现在国内民用较好的产品的导航定位精度基本控制在5~10 m，不太好的设备可能达到几十米甚至几百米，本次设计的导航终端经测试，定位精度约为7 m。

(2) 电子地图显示时间测试
　　当导航设备接收到GPS数据后，如果使用本地电子地图显示当前位置的时间为1 s之内；如果连网下载电子地图，显示当前位置的时间为3 s之内。

(3) 最短路径导航路径规划距离测试
　　通过最短路径规划后，测出从厦门到福州的最短路径是261 km，如果是普通的大路优先算法则是292 km；接着测试从厦门到北京的最短路径距离为2 106 km，如果是普通的大路优先算法，距离则是2 312 km。

结语

　　利用车载导航系统的设计方案，并结合Android系统特性设计的嵌入式系统可嵌入到手机、PDA、POS机、机顶盒、数字电视、家庭媒体播放器等其他终端设备，具有很好的可移植性和可扩展性。在移动导航终端的应用中，以GPS导航为代表的综合信息管理平台将是未来移动终端通信及导航产品的发展趋势，而Android系统在导航终端的应用将会逐步成熟和发展，产品价格也将最终接近大众消费水平，届时导航产品将成为人们休闲、娱乐、旅游探险的必备工具。