论文总字数：31712字

摘 要

随着经济的发展和交通的便利，人们对于导航软件的需求也在逐渐增大。众所周知，导航软件应用一定的路径规划算法对路线进行规划，从而找出客户想要的最佳路线，而随着时代的进步，现代人们的生活节奏也在加快，人们更倾向于将路线总长度最短的路径作为最优路径，从而达到减少出行时间的目的。因此，本次课题将设计实现一个基于路径规划算法的搜索系统。

本次设计实现的系统主要通过Java语言来实现能够搜索从起点到终点的最短路径的核心功能，通过用户注册模块、登录模块以及可以选择三种不同的最短路径算法（包括Dijkstra算法、A*算法、SPFA算法）来具体实现。基于现代交通网的复杂，本系统设计并实现了能够随机生成含有墙壁的地图，也能够由用户自由绘制墙壁形成地图，实现模拟现实地图的复杂性的目的。为了更好地达到节约时间的目的，本系统设置了搜索速度的延迟设置，在0ms模式下，运用任何一种算法都能搜索出准确的最短路径，并且搜索的最短时间少于1秒，大大提高了搜索效率。

本次课题需要完成的工作内容有：

（1）首先对系统需要运用的最短路径算法和技术进行分析与学习

（2）然后对系统进行需求分析，通过将系统划分为不同的模块进行详细的设计

（3）其次对系统进行开发，实现能够构造地图、搜索路径、缩短搜索时间的核心功能

（4）最后对系统进行功能测试，并提出改进的方案

关键词：导航路径规划；Dijkstra算法；A*算法；SPFA算法；最短路径

Research and implementation of path planning algorithm in navigation software

Abstract

With the development of economy and the convenience of transportation, people"s demand for navigation software is gradually increasing. As we all know, navigation software applies a certain path planning algorithm to plan the route, so as to find the best route that customers want. With the progress of the times, the pace of modern people"s life is also accelerating. People tend to take the shortest path as the best path, so as to achieve the purpose of reducing travel time. Therefore, this project will design and implement a search system based on path planning algorithm.

This system mainly realizes the core function of searching the shortest path from the beginning to the end through Java language. It can be realized through user registration module, login module and three different shortest path algorithms (including Dijkstra algorithm, a * algorithm and SPFA algorithm). Based on the complexity of modern transportation network, this system can generate maps with walls randomly and draw maps freely by users to realize the purpose of simulating the complexity of real maps. In order to better achieve the purpose of saving time, the system sets the delay setting of search speed. In 0ms mode, using any algorithm can search out the accurate shortest path, and the shortest search time is less than 1 second, which greatly improves the search efficiency.

The tasks of this project are as follows:

(1) Firstly, the shortest path algorithm and technology that the system needs to use are analyzed and studied

(2) Secondly, the system needs analysis, through the system is divided into different modules for detailed design

(3) Thirdly, the system is developed to realize the core functions of constructing map, searching path and shortening searching time

(4) Finally, the function of the system is tested, and the improvement scheme is proposed

Keywords: Navigation path planning; Dijkstra algorithm; A* algorithm; SPFA algorithm; Shortest path

目录

第一章 绪论 1

1.1 论文工作背景与意义 1

1.2 相关研究现状 2

1.3 主要工作内容 2

1.4 论文组织结构 3

第二章 相关技术基础 4

2.1 最短路径算法 4

2.1.1 Dijkstra算法 4

2.1.2 A*算法 4

2.1.3 SPFA算法（Shortest Path Faster Algorithm） 5

2.2 Eclipse 6

2.2.1 Eclipse简介 6

2.2.2 Eclipse的优点 6

2.2.3 Eclipse的缺点 6

2.3 Maven 6

2.3.1 Maven简介 6

2.3.2 Maven的优点 6

2.3.3 Maven的缺点 6

2.4 MySQL 7

2.4.1 MySQL的简介 7

2.4.2 MySQL的优点 7

2.4.3 MySQL的缺点 7

2.5 本章小结 8

第三章 系统需求分析 9

3.1 系统功能需求分析 9

3.1.1 系统的开发要求 9

3.1.2 用例说明 9

3.2 系统非功能需求分析 10

3.2.1 系统的性能需求 10

3.2.2 系统的可维护性与可扩展性 10

3.2.3 系统的安全性与保密性 11

3.2.4 系统的易用性 11

3.3 本章小结 11

第四章 系统设计 12

4.1 系统总体设计 12

4.2 系统详细设计 13

4.2.1 系统数据库设计 13

4.2.2 系统界面设计 13

4.3 核心算法设计 18

4.3.1 Dijkstra算法的运用 18

4.3.2 A*算法的运用 20

4.3.3 SPFA算法的运用 23

4.4 本章小结 24

第五章 系统实现与测试 25

5.1 系统实现工具与环境 25

5.2 核心代码分析 25

5.3 系统主要运行界面 29

5.3.1 系统随机生成图 29

5.3.2 用户绘制模拟地图 32

5.4 系统测试 32

5.4.1 系统测试环境与工具 32

5.4.2系统功能测试 33

5.4.3 系统非功能测试 34

5.5 本章小结 36

第六章 总结与展望 37

6.1 总结 37

6.2 展望 37

致谢 38

参考文献 39

第一章 绪论

本章节为论文的绪论章节，主要分为三个小节，第一小节主要论述本文工作的背景与意义，了解本文的研究意义；第二小节主要论述了路径规划算法的相关研究现状，结合国内外学术能者的思想成就确定本文设计系统的主要解决方案；第三小节为根据前两个小节的内容提出本系统的主要工作内容；最后的小节论述本文的组织结构。

1.1 论文工作背景与意义

剩余内容已隐藏，请支付后下载全文，论文总字数：31712字