本文着重研究的是图网中任意若干顶点之间的最短路径最优规划。本课题通过使用matlab实现4个经典的随机最短路径派生算法，并将其应用在纽约等6个城市路网数据集上，进行随机规划最优最短路径的模拟，来研究算法各项性能指标，对比其优劣。

案例研究结果表明，本课题所采用的算法，大幅度减少了冗余节点，减轻了复杂度的操作，提高了算法的性能和效率，并且确保课精确度。该算法可以有效应用在多种路径规划类现实应用中，提高工作效率。

本文的研究内容

本文首先介绍了四种比较成熟经典的最短路径算法，然后详述了实际城市路网的交通数据信息的预处理过程，提出了最短路径算法在不同数据集上的运行特点，提出来了在区域搜索策略方面所做的优化与改进之处，最后进行了实验验证。本文的研究目的是对城市交通数据进行预处理后，最大程度地减少最短路径算法的占用空间与时间复杂度。

实验分析中对每种算法都给出了数据集分析，时间复杂度分析，可行性分析，以及综合性能分析。实验效果基于是否能够切实可行的应用在社会生产实践，比较了算法在不同环境下的性能和优缺点，最后得出在何种数据集上应使用具有何种指标的最短路径算法，以及总结了在不同的情况下应该使用何种算法提高效率。通过实验，得出结论与目前先进的城市规划算法发展趋势如出一辙。

本文分为六个章节：

第一章：绪论，先给出了本课题的研究背景与研究意义，之后阐述了最短路径算法的研究历史与研究现状，最后说明了本文的主要研究内容。

第二章：本文的理论。介绍自上世纪60年代以来最短路径算法的研究和发展历史，主要说明了路网中较为成熟的四种最短路径算法与搜索算法，重点研究了 Dijkstra 算法的思想原理，并说明了传统的 Dijkstra 算法存在的缺陷，在理论方面对经典算法以及衍生最短路径算法原理进行阐述并给出本次课题研究的随机的概念。

第三章：本文的方法基础。介绍四种需要研究的最短路径的原理和各自的伪代码示意图，分析每个算法解决的问题领域以及性能指标上的特点，为后续实验做准备。

第四章：在真实数据集上进行最短路径算法实验，通过使用不同数据集在同一算法上进行实验观察同一算法在时间复杂度，性能压力以及准确性上的指标变化情况；同样使用相同数据集在不同算法上实验得出最适合某种社会网络模型的最短路径算法。

第五章：承上一章对于最短路径算法的实验设计以及实验目的，在本章中主要体现所有实验的详细流程及所有的实验结果，并且在实验结果原始数据的基础上进行各项指标的分析，从数据分析中得出最短路径算法的相关适合领域。详述本次实验的五种最短路径算法适合应用的不同社会生产领域，以及在目前炙手可热的滴滴打车等使用随机点的交通规划类系统中有待提升的最短路径规划算法。

第六章：总结与展望。提出了三个创新点，对以后的研究规划了两点展望。基于对上述五个章节所描述以及实验的完备程度做出一个系统客观的总结，基于此指出后续仍然有待改进的地方，为今后继续研究此课题的同学们一个思维上的借鉴，作为以后理论研究位置奋斗的目标。同时我也会在文末公布出本次实验的所有原始数据集，为以后进一步研究的同学留有研究基础。

总结

最短路径是图轮的基础也是网络优化问题的基础，业界研究历史可以追溯到上世纪60年代，一直到先进社会，最短路径问题升级为最优规划问题，依然成为学术界研究的热点。路径的最短，某种程度上降低了成本、节省了时间、节省了人力、节约了资源。这种思维始终适合当今社会的需求，也是我国目前所体现核心价值观相同。故最短路径问题的研究是有价值的、有意义的。

本文首先以介绍最短路径的起源、发展历史以及代表性人物。对最短路径算法进行了一个概念上的解释，同时引入了图论相关内容，算法使用的数据集处理相关操作给定一个理论基础，然后给随机一个既定的解释，对于后续在大规模数据集上进行；其次，引用了真实的数据集在不同的算法上进行实验，对比各个算法在时间、准确性等各个方面的性能以及根据各自的特点总结出各自适合的数据集。给现实社会生产实践一定的引导。