1. 研究目的与意义
最短路径问题由于其在实际生活中运用的普遍性以及实用性，成为数学信息学科和计算机学科的热点问题。随着人民生活水平的不断提高，线上购物需求增加，物流运输发展迅速，加之近两年新冠疫情爆发以及各种极端天气接踵而至，各城市间物资运输频繁，最短路径在今天的交通运输、物流仓储和城市规划等领域仍然发挥着巨大的作用。由于科学技术的不断发展进步，使用应用数学中的图论与计算机算法相结合，有效的解决最短路径问题。城市间运输的最短路径问题是图论中的一个经典问题，其实质是研究两点之间的最短距离，即在由节点构成的路径图中，运用Jarn#180;#305;k–Prim算法和Dijkstra算法，找出一条经过路径的权值总和最短的路径。
2. 研究内容和预期目标
研究内容： 概述国内外分析最短路径问题的理论，分析发展现状。通过对不同的理论和算法进行对比，分析算法的实质思想和内容以及在实际运用中存在的问题，找出未来的发展方向。
拟解决的关键问题：使用jarn#180;#305;k–prim算法和dijkstra算法，结合实际情况，解决当前背景下城市间运输的最短路径问题。
写作提纲：
3. 国内外研究现状
最短路径问题是一个传统的数学问题，在资源分配、路线分析和设计等方面发挥着不可替代的作用。近年来，Dijkstra 算法和Prim算法已广泛应用于许多领域。随着交通和物流行业的快速发展变革，对 Dijkstra 算法和Prim算法的高效运行提出了新的时代要求，关于求解最短路径问题的算法优化也一直是专家和学者的研究热点。
王芝麟等人研究了传统 Dijkstra 算法求解问题的时间和计算次数，并提出了一种运用二叉堆优化后的 Dijkstra 算法．祝国明等把 Dijkstra 算法用于多源点最短路径求解。周冰,卢贝将Dijkstra算法运用于地下物流配送路径优化，对城市中二级配送节点进行配送时的节点选择进行建模，并使用最短路径算法——Dijkstra算法，对模型数据进行了分析，提升路径选择的效率 。谢建平等人改进Dijkstra算法在大型城市轨道交通网计价系统中的应用，克服了传统算法时间冗长的缺陷、增强了设计的可行性、减少了产生误差的可能性、可延展性更强；郭嘉涛等人将最小生成树算法应用于城市道路修建问题，提高了道路修建的效率……
Yong Huang结合工程实例，提出了一种改进的Dijkstra算法。对改进前的Dijkstra算法进行了解释，并将其用于计算矿井避水最短路径，然后提出改进方法，引入等效路径的概念，分析等效路径的影响因素和权重，并计算出发生突水时的最佳避水路径。Trinanda Syahputra等人运用Prim算法确定了阿山区交通运输局的运输路径……4. 计划与进度安排
1.2022年11月底前——完成选题工作；
2.2022年12月底前——完成开题工作和论文培育立项工作；
3.2022年3月底前——完成初稿和选题复查和中期检查工作；
5. 参考文献
[1]王芝麟,乔新辉,马旭,严研.一种基于二叉堆的dijkstra最短路径优化方法[j].工程数学学报,2021,38(05):709-720.
[2]祝国明.基于dijkstra的多源点最短路径求解算法的设计与分析[j].电脑知识与技术,2021,17(16):177-178.
[3]周冰,卢贝.基于dijkstra算法的地下物流配送路径优化研究[j].现代信息科技,2021,5(06):91-95.
